Problem Description

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

Input Format

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 Format

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

3
1 2
2 3
3 3

2

3
1 1
1 1
1 1

0

1
0 0

-1

Hint

【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