#CSPJ1006. 数字游戏(mali)
数字游戏(mali)
题目描述
小 Z 和小 Y 又在玩数字游戏了。
这次的规则是这样的:最开始有两个空的数列 和 ,第 次小 Y 会在数列 和 的末尾分别添加一个数 ,而小 Z 可以将 和 以任意方式重新排序,使得所有 的最大值最小。
请你帮小 Z 在每一次小 Y 给出两个新的数之后,求出 最大值的最小值。
输入格式
从 mali.in 文件输入数据。
第一行包括一个正整数 ,表示小 Y 给出数字的次数。
接下来 行,第 行包括 个正整数 ,表示每一次小 Y 给出的数对。
输出格式
输出到 mali.out 文件。
输出包括 行,对于每一次小 Y 给出的数字,求出所求排列中对应 和 之和的最大值的最小值。
样例
3
2 8
3 1
1 4
10
10
9
3
1 1
2 2
3 3
2
3
4
说明/提示
样例 1 解释
第一组样例解释:
- 第一次询问后:;
- 第二次询问后,小 Z 可以将序列排列为 ,其中 ,最大值为 ,并且通过枚举可以证明,这种方式排列的两个序列,他们的和的最大值最小。
- 第三次询问后, 小 Z 可以将序列排列为 ,其中 ,最大值为 ,并且通过枚举可以证明,这种方式排列的两个序列,他们的和的最大值最小。
数据范围
对于 的数据,有 ;
对于 的数据,有 。