Flipping Cards
本题没有可用的提交语言。
Description
$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.
The first line contains two integers $n$ ($1 \leq n < 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 one integer, denoting the median of all the numbers that are facing up under Grammy's optimal strategy.
Input
The first line contains two integers $n$ ($1 \leq n < 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.
5
3 6
5 2
4 7
6 4
2 8
1
2 1
6
2