CF272C Dima and Staircase

Dima 有一个由 $n$ 级台阶组成的楼梯。第 $1$ 级台阶的高度为 $a_{1}$，第 $2$ 级台阶的高度为 $a_{2}$，最后一级台阶的高度为 $a_{n}$，满足 $1 \leq a_1 \leq a_2 \leq \ldots \leq a_n$。 Dima 决定和这个楼梯玩游戏，他会从上方往楼梯上扔长方体箱子。第 $i$ 个箱子的宽度为 $w_{i}$，高度为 $h_{i}$。Dima 会将每个箱子垂直扔到楼梯的前 $w_{i}$ 级台阶上，即箱子会覆盖第 $1,2,\ldots,w_{i}$ 级台阶。每个被扔下去的箱子都会一直向下掉，直到发生以下两个事件之一： - 箱子的底面碰到某一级台阶的顶面； - 箱子的底面碰到之前扔下去的某个箱子的顶面。 我们只考虑楼梯和箱子的水平面之间的接触，且不考虑角上的接触。具体来说，宽度为 $w_{i}$ 的箱子不会与第 $w_{i}+1$ 级台阶接触。 现在给出楼梯的描述和 Dima 扔箱子的顺序。对于每个箱子，请你求出它落地后，底面所在的高度。假设每个箱子在前一个箱子落地后才会被扔下。

第一行包含一个整数 $n$ $(1 \leq n \leq 10^{5})$，表示楼梯的台阶数。 第二行包含一个非递减序列 $a_1,a_2,\ldots,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}) $，分别表示每个箱子的宽度和高度。 各行数字之间用空格隔开。

输出 $m$ 个整数，每个整数表示对应箱子落地后底面的高度。按输入顺序输出，数之间用换行分隔。 请不要在 C++ 中使用 %lld 格式符读取或输出 64 位整数。推荐使用 cin、cout 流或 %I64d 格式符。

第一个样例的效果如图所示。  由 ChatGPT 5 翻译