Q. Du Cuo Ti Le
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$ a_1,...,a_{2n} $$$. Initially, all numbers are zero.

There are $$$ n $$$ operations. The $$$ i $$$-th operation is represented by two integers $$$ l_i,r_i (1 \le l_i \lt r_i \le 2n, 1 \le i \le n) $$$, which assigns $$$ i $$$ to $$$ a_{l_i},...,a_{r_i-1} $$$. It is guaranteed that all the $$$ 2n $$$ integers, $$$ l_1,l_2,...,l_n,r_1,r_2,...,r_n $$$, are distinct.

You need to perform each operation exactly once, in arbitrary order.

You want to minimize and maximize the value of index $$$i\ (1 \le i \lt 2n)$$$ such that $$$ a_i\neq a_{i+1} $$$ after all $$$ n $$$ operations. Output the minimum and maximum values of index $$$i$$$.

Note that the minimal and maximal values can appear in different performance orders.

Input

The first line contains an integer $$$ n\ (1 \le n \le 5 \times 10^3) $$$.

The $$$ i $$$-th line of the next $$$ n $$$ lines contains a pair of integers $$$ l_i,r_i\ (1 \le l_i \lt r_i \le 2n) $$$. It is guaranteed that all the $$$ 2n $$$ integers, $$$ l_1, l_2, . . . , l_n, r_1, r_2, . . . , r_n $$$, are distinct.

Output

Output two integers in one line denoting the minimal and the maximal value of index $$$i$$$.

Example
Input
5
2 3
6 7
1 9
5 10
4 8
Output
1 9