题解

Dima有一个由n个楼梯组成的楼梯。第一级在a1高度，第二级在a2高度，最后一级在an高度(1≤a1≤a2≤…≤an)。 迪玛决定和楼梯一起玩，所以他从上往楼梯上扔长方形的盒子。第i个盒子的宽度为wi，高度为hi。Dima将每个盒子垂直向下扔到楼梯的第一个wi楼梯上，也就是说，盒子覆盖了编号为1、2、…、wi的楼梯。每个投掷箱垂直向下飞行，直到至少发生以下两种情况之一: 盒子的底部与楼梯的顶部相接; 盒子的底部与之前抛出的盒子的顶部相接触。 我们只考虑楼梯和箱子的水平边的接触，不考虑角落的接触。具体来说，这意味着一个宽度为wi的盒子不能接触到编号为wi + 1的楼梯。 你会看到楼梯的描述和Dima扔箱子的顺序。对于每个箱子，确定落地后箱子底部的高度。假设一个箱子在前一个箱子落地后落下。
Input
第一行包含整数n(1≤n≤10^5)——楼梯的楼梯数。第二行包含一个非递减序列，由n个整数组成，a1, a2，…， an(1≤ai≤10^9;ai≤ai + 1)。 下一行包含整数m(1≤m≤10^5)——盒子的数量。以下每m行包含一对整数wi, hi(1≤wi≤n;1≤hi≤10^9)-第i个投箱的大小。 行中的数字用空格隔开。
Output
打印m个整数-每个箱子的高度，箱子的底部将在着陆后。按输入框中给出的方框的顺序打印答案。 请不要使用%lld说明符在c++中读取或写入64位整数。建议使用cin、cout流或%I64d指定符。 题目你肯定看不懂，看样例和tips吧！！！

这道题，因为题目告诉你这个楼梯数是递增的，所有可以知道，第一层宽度是1，第二层宽度是2，这样类推，所以我们就可以通过，给的箱子宽度去找他可以放在第几层，但是我们又要考虑高度，可能前面的高度太高了，这层就不能放了，也就是会被顶起来
所以我们在找到第几层的时候，再去比较这一层和前面的高度谁高，然后就可以知道放在哪层了，注意，要更新高度