← 返回题目列表

Codeforces · 272/C

C. 迪玛和楼梯

中文机器翻译题面 查看原题

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

注意

第一个样本如图所示。