题目描述

Dima 有一段由 $n$ 级台阶组成的楼梯。第 1 级台阶的高度为 $a_1$，第 2 级为 $a_2$，最后一级为 $a_n$（$1 \le a_1 \le a_2 \le \ldots \le a_n$）。

Dima 决定玩弄这段楼梯：从上方往楼梯上扔长方体箱子。第 $i$ 个箱子的宽度为 $w_i$、高度为 $h_i$。Dima 把每个箱子竖直地扔向楼梯最前面的 $w_i$ 级台阶，即箱子恰好盖住编号为 $1, 2, \ldots, w_i$ 的台阶。每个被扔出的箱子竖直下落，直到下列事件之一发生：

• 箱子底面碰到某级台阶的顶面；
• 箱子底面碰到先前扔下的某个箱子的顶面。

我们只考虑台阶与箱子水平面的接触，只碰角不算接触。特别地，这意味着宽度为 $w_i$ 的箱子不可能碰到编号为 $w_i + 1$ 的台阶。

给定楼梯的描述以及 Dima 扔箱子的顺序，对每个箱子求出它落定后底面的高度。每个箱子都在前一个箱子落定后才下落。

输入格式

第一行包含整数 $n$（$1 \le n \le 10^5$），表示楼梯的台阶数。第二行包含一个由 $n$ 个整数组成的不下降序列 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$，$a_i \le a_{i+1}$）。

下一行包含整数 $m$（$1 \le m \le 10^5$），表示箱子数。接下来 $m$ 行，每行两个整数 $w_i$、$h_i$（$1 \le w_i \le n$，$1 \le h_i \le 10^9$），表示第 $i$ 个箱子的尺寸。

行内数字用空格隔开。

输出格式

对每个箱子输出一行：该箱子落定后底面的高度。

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

1
3
4
6

3
1 2 3
2
1 1
3 1

1
3

1
1
5
1 2
1 10
1 10
1 10
1 10

1
3
13
23
33

说明/提示

第一组样例如图所示。