题目内容

系统记录了 $n$ 个预约，每个预约占用一段连续的整数秒，表示为闭区间 $[l, r]$，即从 $l$ 到 $r$（包含两端）之间的每一个整数秒都被占用。

请你找出最小的非负整数秒 $t$，使得 $t$ 不被任何一个预约区间所覆盖。换句话说，不存在预约区间 $[l_i, r_i]$ 满足 $l_i \le t \le r_i$。

约束：预约数量 $n$ 满足 $1 \le n \le 2 \times 10^5$；每个区间的左右端点均为整数且满足 $0 \le l \le r \le 10^{18}$。

输入描述

第一行包含一个整数 $n$，表示预约的个数。 接下来 $n$ 行，每行包含两个整数 $l$ 和 $r$，表示一个预约占用的闭区间 $[l, r]$。 数据保证 $n$ 不超过 $2 \times 10^5$，且 $0 \le l \le r \le 10^{18}$。

输出描述

输出一个整数，表示第一个未被任何预约占用的整数秒。

样例1

输入

4
0 5
3 7
6 10
12 15

输出

11

说明

将区间按起点排序后依次处理：

• 初始最早空闲时刻 ans = 0。
• 区间 $[0, 5]$：由于 $0 \le 0 \le 5$，ans 被占用，更新为 $5 + 1 = 6$。
• 区间 $[3, 7]$：此时 $3 \le 6 \le 7$，ans 仍被占用，更新为 $7 + 1 = 8$。
• 区间 $[6, 10]$：此时 $6 \le 8 \le 10$，ans 被占用，更新为 $10 + 1 = 11$。
• 区间 $[12, 15]$：起点 12 > 11，说明时刻 11 未被该区间及之前任何区间覆盖，算法终止。

因此第一个空闲时刻为 11。

样例2

输入

2
1 3
4 6

输出

0

说明

所有区间的起点均大于 0，时刻 0 不在任何预约区间内。

• 初始 ans = 0。
• 第一个区间 $[1, 3]$：起点 1 > 0，ans = 0 不被覆盖，直接得到答案。

因此输出 0。

样例3

输入

3
0 0
2 2
4 4

输出

1

说明

预约占用的是三个孤立时刻 0、2、4。

• 初始 ans = 0。
• 区间 $[0, 0]$：$0 \le 0 \le 0$，ans 被占用，更新为 $0 + 1 = 1$。
• 区间 $[2, 2]$：起点 2 > 1，说明时刻 1 未被占用，算法停止。

因此最小的空闲秒为 1。