M. Flipping Cards
time limit per test
2.5 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$n$$$ cards are placed in a row, where $$$n$$$ is an odd number. Each card has numbers written on both sides. On the $$$i$$$-th card, $$$a_i$$$ is facing up and $$$b_i$$$ is facing down.

Grammy wants to maximize the median of all the numbers that are facing up. In order to achieve this, she can do the following operation at most once.

  • Choose an interval $$$[l,r]$$$ and flip all the cards in the interval. After flipping the cards, $$$b_i$$$ will be facing up and $$$a_i$$$ will be facing down for $$$i \in [l,r]$$$.

Please help Grammy to calculate the median of all the numbers that are facing up under her optimal strategy.

Recall that the median of a sequence of numbers is the $$$\frac{n+1}{2}$$$-th largest number in the sequence.

Input

The first line contains two integers $$$n$$$ ($$$1 \leq n \lt 3 \cdot 10^5, n \bmod 2 = 1$$$), denoting the number of cards.

Each of the next $$$n$$$ lines contains $$$2$$$ integers $$$a_i,b_i$$$ ($$$1 \leq a_i,b_i \leq 10^9$$$), denoting the initial number that is facing up and the initial number that is facing down for each card.

Output

Output one integer, denoting the median of all the numbers that are facing up under Grammy's optimal strategy.

Examples
Input
5
3 6
5 2
4 7
6 4
2 8
Output
6
Input
1
2 1
Output
2