Cheater Search

Interview

Time limit2sMemory limit1024 MB

Summary

Find a contiguous cheater interval [l, r] so that cheaters' claimed ranges avoid it and every non-cheater's claimed range overlaps it.

Level: Medium6 of 10
Topics: Two pointers, Prefix sum, Array
Solved: No attempts yet

Problem

There are $N$ pidols numbered from $1$ to $N$ , all distinct. Some of them are cheaters, and their numbers are consecutive. Specifically, for some integers $l$ , $r$ $(1 \leq l \leq r \leq N)$ , pidols $l$ through $r$ are all cheaters, and every other pidol is not a cheater.

Pidol $i$ claims that at least one cheater is among the pidols numbered from $a_i$ to $b_i$ inclusive. If pidol $i$ is not a cheater, the claim is true. However, all cheaters lie. That is, if pidol $i$ is a cheater, then no cheater is among the pidols numbered $a_i$ to $b_i$ .

Input

The first line contains the number of pidols $N$ . $(2 \leq N \leq 200\ 000)$

Each of the next $N$ lines contains two integers $a_i$ and $b_i$ , separated by a space. The line $i+1$ gives the claim of pidol $i$ , that at least one cheater is among the pidols numbered from $a_i$ to $b_i$ . $(1 \leq a_i \leq b_i \leq N)$

Output

Print two integers $l$ and $r$ separated by a space, a valid pair that satisfies all the claims. If several answers exist, print any one of them.

Examples1

Example 1
Input
```
6
3 4
4 5
1 1
1 4
1 2
2 6
```
Expected output
```
2 3
```