A. 两个序列的中位数

内存限制:256 MiB 时间限制:500 ms 输入文件: zhong.in 输出文件: zhong.out
题目类型:传统 评测方式:文本比较

题目描述

中位数:给定一个 N 个整数构成的递增序列,中位数是中间位置的数字。如果一共有奇数个数,则中位数是最中间的数;如果一共有偶数个数,则中位数是中间偏左的数。

例如 S1={11,12,13,14} 的中位数是 12,S2={9,10,15,16,17} 的中位数是 15。

两个序列的中位数:定义为包含两个序列的所有元素的非递减序列的中位数。

例如,S1 和 S2 的中位数为 13。

给定两个递增序列,请你找出它们的中位数。

输入格式

共两行,每行包含一个递增序列。

每行首先包含一个整数 N,表示序列长度,接下来包含 N 个整数,表示完整序列。

输出格式

输出一个整数,表示两个序列的中位数。

样例

输入样例:

4 11 12 13 14
5 9 10 15 16 17

输出样例:

13

数据范围与提示

1≤N≤2×10^5 ,

序列中的整数都在 int 范围内。