P16250 [蓝桥杯 2026 省研究生组] 人类识别审查

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 $。

### 【评测用例规模与约定】 对于 $ 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 $。