Description

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

Samples

2
1 3
2 4

1 3

Resources

The 21st UESTC Programming Contest Preliminary