题目描述

有一支队伍包含 $n$ 名首发选手，$n$ 保证为奇数。第 $i$ 名首发选手的战力为 $a_i$，并且有一名对应替补选手，战力为 $b_i$。

比赛前可以至多进行一次替换操作：选择一个区间 $[l,r]$，将区间内每个位置的首发选手和对应替补选手交换。也可以不进行任何替换。

最终出战的 $n$ 名选手战力的中位数定义为第 $\dfrac{n+1}{2}$ 大的战力。求通过至多一次区间替换后，中位数的最大可能值。

输入格式

第一行一个奇数 $n$，表示首发选手数量。

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

输出格式

输出一行一个整数，表示最大的战力中位数。

5
6 4
2 8
4 7
5 2
3 6

6

1
2 3

3

样例解释

样例 1 中，可以交换区间 $[2,3]$，此时出战战力为 $6,8,7,5,3$，第 $3$ 大的数为 $6$，可以达到最大中位数 $6$。

样例 2 中，只有一个位置，可以选择交换第 $1$ 个位置，使出战战力从 $2$ 变为 $3$。

数据范围与约定

特殊性质 A：所有 $a_i,b_i$ 均为 $0$ 或 $1$。

对于所有数据，$1 \le n \le 3\times 10^5$，$n$ 为奇数。

下发样例

下发样例下载