Aryo 的 2418 岁生日有很多间隔。他真的很兴奋,决定用一些颜色来为所有这些间隔着色。他为自己制定了一个简单的规则。如果不存在同时满足以下条件的三个区间 a、b 和 c,他称着色为“好”:
- a、 b 和 c 的颜色相同,
- $$a \cap b \neq \varnothing$$,
- $$b \cap c \neq \varnothing$$,
- $$a \cap c = \varnothing$$。
此外,他发现对于每个区间 i 和 j,i 中至少有一个点不在 j 中。
给定一组间隔。你必须找到最小的数字 k,这样 Aryo 才能找到 k 种颜色的漂亮颜色。
输入
第一行包含一个整数 n (1 ≤ n ≤ 103),即间隔数。
以下 n 行每行包含一个区间描述。每个区间由两个数字 si、ei 描述,它们是该区间的起点和终点(- 105 < si,ei < 105,si ≤ ei)。为清楚起见,请参阅示例。方括号代表包含对应的端点,圆括号代表排除对应的端点。
输出
写一个整数 k — 良好着色所需的最小颜色数。
示例
输入 #1
2 [1,2) (3,4]
输出 #1
1
输入 #2
3 [1,3] [2,6] (5,7)
输出 #2
2