分数: 575 点
问题陈述
有 2N 成对不同点,编号为 1 to 2N,在一个圆圈上。从点出发 1 顺时针方向,点排列为点 2,点 3, ..., 点 2N.
你被给予 N 这个圆上的和弦。的端点 i第和弦是点 A_i 和 B_i,以及 2N 值 A_1,\ldots,A_N,B_1,\ldots,B_N 都是不同的。
在此圆上依次执行以下操作各一次:
- 其中 N 和弦,选择任意数量的和弦,使两个选定的和弦不相交,然后删除剩余的和弦。
- 向圆中自由添加一个和弦。
求运算完成后弦之间最大可能的交点数。
约束
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_i,B_i \leq 2N
- 的 2N 值 A_1, \ldots, A_N,B_1,\ldots,B_N 成对不同。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
输出答案。
示例输入 1
3 1 5 6 3 4 2
示例输出 1
2
最初,有 3 和弦放在圆上,如图所示。
删除和弦连接点后 3 和 6 并通过运算添加新的和弦,则和弦之间的交点个数为 2.

不可能使弦之间的交点数量 3 或更多,所以答案是 2.
最后添加的弦的端点不需要是任何点 1,\ldots, 2N.
示例输入 2
4 1 8 2 7 3 6 4 5
示例输出 2
4
示例输入 3
3 1 2 3 4 5 6
示例输出 3
2