题目描述

Z 苦于自己每次打游戏都玩的差，被对手次次打爆，决定自己成立一支职业的游戏战队，在这个战队中，有 $n$ 个首发选手，第 $i$ 个首发选手的战力以一个整数 $a_i$ 表示，同时每个首发选手 $i$ 都对应一个替补选手，第 $i$ 个首发选手对应的替补选手的战力为 $b_i$。Z 每场比赛之前可以进行至多一次选手替换，进行选手替换时 Z 可以选择一个区间 $[l,r](1\le l\le r\le n)$，然后将区间内的所有首发选手与其对应的替补选手进行交换，选手替换后，未被交换的首发选手和被交换的替补选手（共 $n$ 名）会代表 Z 的战队出战。

现在 Z 即将带领战队参战，Z 已经提前通过预测得知了出战的 $n$ 名选手的战力的中位数越大表明战队越强，所以请你告诉 Z，Z 的战队出战的 $n$ 名选手战力的中位数最大是多少？

$n$ 名选手战力的中位数为这些选手的战力中第 $\dfrac{n+1}{2}$ 大的战力，因为 Z 的数学不好，因此 Z 只会招募奇数名首发选手和他们对应的替补。

输入格式

第一行一个整数 $n$，表明 Z 的战队的首发选手数目，保证 $n$ 为奇数。

接下来 $n$ 行，每行两个以空格隔开的整数 $a_i,b_i$，分别表示第 $i$ 名首发选手的战力和第 $i$ 名首发选手对应的替补选手的战力。

输出格式

一行一个整数，表明最大的战力中位数。

5
6 4
2 8
4 7
5 2
3 6

6

1
2 3

3

见 sample3.in

见 sample3.ans

见 sample4.in

见 sample4.ans

数据规模与约定

对于 $20\%$ 的测试数据，满足 $1\le n\le 200$；

对于另外 $35\%$ 的测试数据，满足 $1\le n\le 2000$；

对于另外 $10\%$ 的测试数据，满足 $0\le a_i,b_i\le 1$；

对于 $100\%$ 的测试数据，满足 $1\le n\le 3\times 10^5$，$0\le a_i,b_i\le 2\times 10^9$ ，保证 $n$ 一定为奇数。

大样例

大样例下载