CF272C.Dima and Staircase

Dima's got a staircase that consists of n stairs. The first stair is at height _a_1, the second one is at _a_2, the last one is at a__n (1 ≤ _a_1 ≤ _a_2 ≤ ... ≤ a__n).

Dima decided to play with the staircase, so he is throwing rectangular boxes at the staircase from above. The i-th box has width w__i and height h__i. Dima throws each box vertically down on the first w__i stairs of the staircase, that is, the box covers stairs with numbers 1, 2, ..., w__i. Each thrown box flies vertically down until at least one of the two following events happen:

• the bottom of the box touches the top of a stair;
• the bottom of the box touches the top of a box, thrown earlier.

We only consider touching of the horizontal sides of stairs and boxes, at that touching with the corners isn't taken into consideration. Specifically, that implies that a box with width w__i cannot touch the stair number w__i + 1.

You are given the description of the staircase and the sequence in which Dima threw the boxes at it. For each box, determine how high the bottom of the box after landing will be. Consider a box to fall after the previous one lands.

迪马有一段由 $n$ 级台阶组成的楼梯。第一级台阶高度为 $a_1$，第二级为 $a_2$，最后一级为 $a_n$（满足 $1 \le a_1 \le a_2 \le \cdots \le a_n$）。

迪马决定和这段楼梯玩一个游戏：他从上方朝楼梯垂直投掷若干矩形箱子。第 $i$ 个箱子的宽度为 $w_i$、高度为 $h_i$。迪马将每个箱子垂直向下投掷到楼梯的前 $w_i$ 级台阶上，即该箱子覆盖编号为 $1, 2, \ldots, w_i$ 的台阶。每个被投出的箱子垂直下落，直到发生以下两个事件之一时停止：

• 箱子底面接触到某级台阶的顶面；
• 箱子底面接触到之前已投出并已落地的某个箱子的顶面。

我们仅考虑台阶与箱子的水平边之间的接触，不考虑角点接触。特别地，这意味着一个宽度为 $w_i$ 的箱子无法接触到编号为 $w_i + 1$ 的台阶。

现给出楼梯的描述以及迪马投掷箱子的顺序。对每个箱子，请确定其落地后底面所处的高度。注意：每个箱子均在前一个箱子落地之后才开始下落。

The first line contains integer n (1 ≤ n ≤ 105) — the number of stairs in the staircase. The second line contains a non-decreasing sequence, consisting of n integers, _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109; a__i ≤ a__i + 1).

The next line contains integer m (1 ≤ m ≤ 105) — the number of boxes. Each of the following m lines contains a pair of integers w__i, h__i (1 ≤ w__i ≤ n; 1 ≤ h__i ≤ 109) — the size of the i-th thrown box.

The numbers in the lines are separated by spaces.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 楼梯的阶数。
第二行包含一个非递减序列，由 $n$ 个整数 $a_1, a_2, \dots, a_n$ 组成（$1 \leq a_i \leq 10^9$；$a_i \leq a_{i+1}$）。

接下来一行包含一个整数 $m$（$1 \leq m \leq 10^5$）—— 箱子的数量。
随后的 $m$ 行中，每行包含一对整数 $w_i, h_i$（$1 \leq w_i \leq n$；$1 \leq h_i \leq 10^9$）—— 第 $i$ 个被扔下的箱子的尺寸。

各行中的数字以空格分隔。

Print m integers — for each box the height, where the bottom of the box will be after landing. Print the answers for the boxes in the order, in which the boxes are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出 m 个整数——对每个箱子，输出其落地后底部所在的高度。请按照输入中给出箱子的顺序输出对应答案。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

The first sample are shown on the picture.

第一个样例展示在图片中。