解题思路

要求找到最小的非负整数 $x$，使得 $x$ 不在任何一个闭区间 $[l_i,r_i]$ 中。

可以使用排序加区间合并的思想。

核心做法如下：

1. 令答案候选值 $ans=0$，表示当前最小可能不被覆盖的非负整数。

题目内容

给定 $n$ 段闭区间 $\{[l_1,r_1],[l_2,r_2],\dots,[l_n,r_n]\}$，请你计算最小的非负整数 $x$，使得 $x$ 不落在任何一个区间内（即不存在 $i$ 使得 $l_i \le x \le r_i$）。

输入描述

第一行输入一个整数 $n\ (1 \le n \le 2 \times 10^5)$，表示区间的数量。

此后 $n$ 行，每行输入两个整数 $l,r\ (0 \le l \le r \le 10^{18})$，表示一个闭区间 $[l,r]$。

输出描述

输出一个整数，表示所求的最小非负整数。

样例1

输入

3
0 2

输出

3

说明

区间为 $[0,2]$，所有非负整数中，$0,1,2$ 均在区间内，$3$ 是第一个不在任何区间内的非负整数。