Dima 有一个由 n 个楼梯组成的楼梯。第一个楼梯的高度为 a1,第二个楼梯的高度为 a2,最后一个楼梯的高度为 an (1 ≤ a1 ≤ a2 ≤ ... ≤ an)。
迪马决定玩楼梯,所以他从上面向楼梯扔矩形盒子。第 i 个盒子的宽度为 wi,高度为 hi。迪玛将每个盒子垂直向下扔到楼梯的第一个wi楼梯上,即盒子覆盖了数字1、2、...、wi的楼梯。每个抛出的盒子都会垂直向下飞行,直到至少发生以下两个事件之一:
- 盒子的底部接触楼梯的顶部;
- 盒子的底部接触到之前抛出的盒子的顶部。
我们只考虑楼梯和盒子水平面的接触,不考虑角落的接触。具体来说,这意味着宽度为 wi 的盒子不能接触楼梯编号 wi + 1。
你会得到楼梯的描述以及迪玛向楼梯扔箱子的顺序。对于每个盒子,确定着陆后盒子底部的高度。考虑一个盒子在前一个盒子落地后掉落。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 楼梯中的楼梯数量。第二行包含一个非递减序列,由 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109; ai ≤ ai + 1) 组成。
下一行包含整数 m (1 ≤ m ≤ 105) — 盒子的数量。以下 m 行中的每一行都包含一对整数 wi, hi (1 ≤ wi ≤ n; 1 ≤ hi ≤ 109) — 第 i 个抛出的盒子的大小。
行中的数字以空格分隔。
输出
打印 m 个整数 — 每个盒子的高度,即落地后盒子底部的高度。按顺序打印方框的答案,其中方框是在输入中给出的。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
5 1 2 3 6 6 4 1 1 3 1 1 1 4 3
输出 #1
1 3 4 6
输入 #2
3 1 2 3 2 1 1 3 1
输出 #2
1 3
输入 #3
1 1 5 1 2 1 10 1 10 1 10 1 10
输出 #3
1 3 13 23 33
注意
第一个样本如图所示。