关键观察

• 由于初始 $a$ 非降：$a_1\le a_2\le \dots \le a_n$。
• 对于一个宽为 $w_i$ 的新方块，落地位置是当前前缀区间 $[1,w_i]$ 的最高高度。
• 把“已经被之前的方块整体抬高的最左前缀”的统一高度记为 $base$，初始 $base=0$。

那么每次有：

• 当前方块的底部高度

题目内容

相信大家都玩过俄罗斯方块，本题提供一个新版供大家体验——静止版俄罗斯方块，简单规则如下：

1. 游戏为玩家提供一个高度无限，宽度为 $n$ 的界面，并且具有一个初始状态，包含 $n$ 列不可破坏的方块，每一列宽度为 $1$ ，高度为 $a_i$ ；
2. 游戏开始后，会有 $m$ 个矩形方块依次贴着界面最左边从无限高处下落，每个方块宽 $w_i$ 高 ；
3. 和传统的俄罗斯方块游戏一样，一旦下落的矩形方块碰到任意方块，就会立即停止下落。遗憾的是，正如游戏的名字一样，在这个过程中玩家无法进行对方块进行任何操作，但是游戏换了一个玩法：请玩家回答游戏过程中每个下落的矩形方块在停止下落后底部的高度是多少。

输入描述

第一行输入一个正整数 $n(1≤n≤100000)$，表示游戏界面宽度。

第二行输入 $n$ 个正整数 $a_i(1≤a_i≤10^9,a_1≤a_2≤...≤a_n)$，表示游戏初始状态。

第三行输入一个正整数 $m$,$(1≤m≤100000)$ ，表示游戏过程中下落的矩形方块个数。

接下来 $m$ 行，每行包含两个数字 $w_i$ 和 $h_i(1≤w_i≤n,1≤h_i≤10^9)$ ，中间用空格隔开，代表一个方块的宽和高。

输出描述

一共输出 $m$ 行答案，代表每个方块底部所处的高度。

样例1

输入

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

输出

1
3
4
6