题目描述

2145 年，全球通过《合成人管控法案》，所有疑似伪装的高仿生 AI 都必须接受“人类识别审查”。

新港区的审讯室内，小蓝盯着桌面投影出来的名单：房间里一共有 $N$ 个“智能体”，外表与行为几乎与人类无异，其中有些是真正的人类，有些则是伪装的人形 AI。

审查规则如下：

1. 设房间里真正的人类数量为 $K$（$K$ 为整数，满足 $0 \leq K \leq N$）。
2. 第 $i$ 个智能体给出一段证词：“人类数量在区间 $[a_i, b_i]$ 内。”
3. 若某个智能体是真正的人类，则它的证词必定为真，即 $a_i \leq K \leq b_i$。
4. 若某个智能体是伪装的 AI，则它的证词必定为假，即 $K \notin [a_i, b_i]$。

作为小蓝的助手，请你分析所有证词，计算出房间里最多可能有多少个人类（即最大可能的 $K$ 值）。如果不存在任何逻辑自洽的 $K$，输出 $-1$。

输入格式

第一行输入一个整数 $N$，表示房间里智能体的数量。

接下来 $N$ 行，每行输入两个整数 $a_i, b_i$，表示第 $i$ 个智能体声称的人类数量区间。

输出格式

输出一个整数，表示满足条件的最大 $K$；若无解输出 $-1$。

3
1 2
2 3
3 3

2

3
1 1
1 1
1 1

0

1
0 0

-1

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \leq N \leq 10^3$，$0 \leq a_i \leq b_i \leq N$；

对于所有评测用例，$1 \leq N \leq 10^5$，$0 \leq a_i \leq b_i \leq N$。