P16250 [Lanquiao Cup 2026 NOI Qualifier Graduate Group] Human Identification Review

In the year 2145, the world passed the "Synthetic Human Control Act". All suspected disguised high-bionic AI must undergo a "human identification review". In the interrogation room of Xingang District, Xiaolan stared at the list projected on the table: there are a total of $N$ "agents" in the room, whose appearance and behavior are almost indistinguishable from humans. Some are real humans, and some are humanoid AI in disguise. The review rules are as follows: 1. Let the number of real humans in the room be $K$ ($K$ is an integer satisfying $0 \leq K \leq N$). 2. The $i$-th agent gives a testimony: "The number of humans is within the interval $[a_i, b_i]$." 3. If an agent is a real human, then its testimony must be true, i.e., $a_i \leq K \leq b_i$. 4. If an agent is a disguised AI, then its testimony must be false, i.e., $K \notin [a_i, b_i]$. As Xiaolan's assistant, please analyze all testimonies and compute the maximum possible number of humans in the room (i.e., the largest possible value of $K$). If there is no logically consistent $K$, output $-1$.

The first line contains an integer $N$, representing the number of agents in the room. The next $N$ lines each contain two integers $a_i, b_i$, representing the interval of the number of humans claimed by the $i$-th agent.

Output one integer, the maximum $K$ that satisfies the conditions; if there is no solution, output $-1$.

### 【Constraints and Conventions】 For $30\%$ of the testdata, $1 \leq N \leq 10^3$, $0 \leq a_i \leq b_i \leq N$. For all testdata, $1 \leq N \leq 10^5$, $0 \leq a_i \leq b_i \leq N$. Translated by ChatGPT 5