该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem:南师大奇谈

时间限制：1s

空间限制：2,000,000KiB

Background && Description

​ 原力清理大师到最后也没等来你的帮助，气喘吁吁爬~~（字面意思）上了楼顶。但是直到此刻，当原力清理大师站在楼顶享受烈日曝晒~~校园的美丽风景时，才明白美丽大方的wq老师的良苦用心。要想看得更远，不妨先站在巨人的肩膀上。

​ 为此，原力清理大师来到了学校的后山。奇妙的是，在这里他碰到了南师大的山神。山神将南师大后山排成一列，绵延不绝。山神告诉原力清理大师，现在南师大共有 $n$ 座山，每座山的高度是 $a_i$ 。

​ 现在，山神将询问原力清理大师将某座山增高之后的影响，共询问 $q$ 次。假设原力清理大师此时正处于第 $i$ 座山，他向右看去，第一个高度超过（不包括一样高）他当前所在的山的山视为挡住他的视线，且无论后面的山有多高，都视为该山挡住他的视线。若山神此时将两座山之间的某一座山的高度增加 $h$ ，使其挡住原力清理大师的视线，则视为这座山对第 $i$ 座山产生影响。

​ 现在，原力清理大师的脑子因为熬夜已经彻底生锈了。虽然你上一次无情地鸽掉了他的提问，但是迫于无奈，他不得不再次死皮赖脸地向你请教这 $q$ 次询问的答案。

Input Format

​ 第一行为一个整数 $n$ ，代表南师大此刻山的数量。

​ 第二行为 $n$ 个正整数，每个数代表第 $i (1 \le qi \le qn)$ 座山的高度 $a_i$ 。

​ 第三行为一个正整数 $q$ ，代表山神向原力清理大师询问的次数。

​ 接下来 $q$ 行，每行两个正整数，分别代表山神想要将第 $i$ 座山的高度增加 $h_i$ 。

Output Format

输出 $q$ 行，每行一个整数，代表山神若增高了某座山，会产生影响的山的数量 。

Data Range

• 对于 $50$ 的数据，$1 \leq n\leq 1000$ ；对于 $100$ 的数据， $1 \leq n\leq 100000$ 。
• 对于 $50$ 的数据，$1 \leq q\leq 1000$ ；对于 $100$ 的数据， $1 \leq q\leq 100000$ 。
• 对于 $100$ 的数据， $1 \leq q\leq n$ ；对于 $50$ 的数据，$1 \leq h\leq 10000000$ ；对于 $100$ 的数据， $1 \leq h\leq 100000$ 。
• q次询问独立，互不影响。

Input Example #1：

6
1 4 2 8 5 7
2
5 4
2 3

Output Example #1：

1
0

Example Explanation：

​ 第五座山增高后超过了第四座山，对其产生了影响；第二座山无论增高多少，都比第一座山高，不产生影响。

$Attention:$ 山神只是想想，不是真的要把山增高哟。