题目描述

Ayimok 是一位魔法师。

他每天的任务是将魔法瓷砖排成一条直线，然后施展魔法咒语。

魔法瓷砖及其排列遵循以下规则：

• 每个魔法瓷砖的形状为高度为 1 的梯形。

• 一些魔法瓷砖可能与其他魔法瓷砖重叠。

• 魔法瓷砖在二维坐标系上排列。

• 魔法瓷砖的上边缘位于一个水平线上，其 y 坐标为 1。

• 魔法瓷砖的下边缘位于一个水平线上，其 y 坐标为 0。

他在完成施展魔法咒语后必须将这些魔法瓷砖移开。一天，他发现移走许多魔法瓷砖非常繁琐，于是决定简化这个过程。

现在，他学会了 "磁化咒语"，可以高效地移除魔法瓷砖。这个咒语可以一次性移除一组魔法瓷砖。集合中的任意两个魔法瓷砖都必须互相重叠。

例如，在图 1 中，他可以对所有三个魔法瓷砖施展磁化咒语，一次性将它们全部移走，因为它们彼此重叠。（请注意，为了便于理解，魔法瓷砖的高度被有意改变）

图 1：可以一次性移除的魔法瓷砖集合

然而，在图 2 中，他无法同时对三个魔法瓷砖施展磁化咒语，因为瓷砖 1 和瓷砖 3 不重叠。

图 2：无法一次性移除的魔法瓷砖集合

他希望以尽可能少的磁化咒语移除所有魔法瓷砖，因为施展该咒语会消耗魔力。

让我们考虑图 3 的情况。他可以通过三次施展磁化咒语将所有魔法瓷砖全部移除；第一次施展咒语移除瓷砖 1 和 2，第二次施展咒语移除瓷砖 3 和 4，第三次施展咒语移除瓷砖 5 和 6。

图 3：移除所有魔法瓷砖的一种方法（非最小次数）

实际上，他只需要两次施展磁化咒语就可以移除所有魔法瓷砖；第一次施展咒语移除瓷砖 1、2 和 3，第二次施展咒语移除瓷砖 4、5 和 6。这是移除所有魔法瓷砖所需的最小咒语次数。

图 4：移除所有魔法瓷砖的最优方法（最小次数）

给定一组魔法瓷砖，你的任务是创建一个程序，输出移除所有这些魔法瓷砖所需的最小磁化咒语次数。

可能会有一个魔法瓷砖与其他瓷砖不重叠，但他仍然需要施展磁化咒语将其移除。

---

输入

输入遵循以下格式：

$N$

$xLower_{11}$ $xLower_{12}$ $xUpper_{11}$ $xUpper_{12}$

$xLower_{21}$ $xLower_{22}$ $xUpper_{21}$ $xUpper_{22}$

$xLower_{31}$ $xLower_{32}$ $xUpper_{31}$ $xUpper_{32}$

:

:

$xLower_{N1}$ $xLower_{N2}$ $xUpper_{N1}$ $xUpper_{N2}$

第一行包含一个整数 $N$，表示魔法瓷砖的数量。

接下来是 $N$ 行，包含魔法瓷砖的信息。

第 $(i+1)$ 行包括四个整数 $xLower_{i1}$、$xLower_{i2}$、$xUpper_{i1}$ 和 $xUpper_{i2}$，表示第 $i$ 个魔法瓷砖的四个角点位于 $(xLower_{i1}, 0)$、$(xLower_{i2}, 0)$、$(xUpper_{i1}, 1)$ 和 $(xUpper_{i2}, 1)$ 处。

您可以假设没有两个魔法瓷砖会共享它们的角点。也就是说，所有 $xLower_{ij}$ 是不同的，所有 $xUpper_{ij}$ 也是不同的。输入满足以下约束条件：

• $1 \\leq N \\leq 10^5$

• $1 \\leq xLower_{i1} < xLower_{i2} \\leq 10^9$

• $1 \\leq xUpper_{i1} < xUpper_{i2} \\leq 10^9$

• 所有 $xLower_{ij}$ 互不相同。

• 所有 $xUpper_{ij}$ 互不相同。

输出

您的程序必须输出移除所有魔法瓷砖所需的最小磁化咒语次数。

---

示例输入1

3
26 29 9 12
6 10 15 16
8 17 18 19

示例输出1

1

---

示例输入2

3
2 10 1 11
5 18 9 16
12 19 15 20

示例输出2

2

---

示例输入3

6
2 8 1 14
6 16 3 10
3 20 11 13
17 28 18 21
22 29 25 31
23 24 33 34

示例输出3

2

---

来源

2013 年夏令营

---