题目描述

王老师有一个楼梯，由 n 阶台阶组成。台阶从左到右的高度依次为a1, a2, …, an（1 <= a1 <= a2 … <= an）。王老师决定在楼梯上玩抛箱子的游戏来淘汰站在楼梯上的学生。王老师将宽度为 wi，高度为 hi 的箱子对齐楼梯左上角垂直放下，箱子会掉到楼梯上。箱子掉落在楼梯上的位置规定如下：
箱子底部碰到楼梯或是其他箱子顶部就会水平停放在该位置。
王老师连续将 m 个箱子抛出后，求每个箱子的停放高度。
注：抛出箱子的顺序不能更改。

输入格式

第一行一个整数 n，表示 n 阶台阶。
第二行为台阶高度 ai。
第三行一个整数 m，表示 m 个箱子。
接下来 m 行，每行 2 个整数 wi, hi，表示箱子的宽度和高度。

输出格式

输出 m 个整数，表示每个箱子最后停留的高度

样例1

输入

5
1 2 3 6 6
4
1 1
3 1
1 1
4 3

输出

1
3
4
6

样例2

输入

3
1 2 3
2
1 1
3 1

输出

1
3

数据范围

对于 30%的数据，1 <= n <= 20, 1 <= ai <= 100; ai <= ai + 1, 1 <= m <= 50, 1 <= wi <= n,1 <= hi <= 100；
对于 100%的数据，1 <= n <= 10 ^ 5, 1 <= ai <= 10 ^ 9; ai <= ai + 1, 1 <= m <= 10 ^ 5, 1 <= wi <= n, 1 <= hi <= 10 ^ 9。

限制

1s

样例解释

样例 1 如图所示：

来源

Codeforce272C
CWOI新高二专题测试八