AT_abc426_f [ABC426F] Clearance

AtCoder Inc. 的在线商店当前销售 $N$ 种商品，第 $i$ 种商品的库存为 $A_i$ 件。 依次处理下面 $Q$ 个订单。第 $i$ 个订单如下： - 每种编号为 $l_i, l_i+1, \dots, r_i$ 的商品，各购买 $k_i$ 件。如果某商品剩余不足 $k_i$ 件，则购买全部剩余库存。请报告在本次订单中总共购买了多少件商品。 需要注意的是，对 $i < Q$，在处理第 $(i+1)$ 个订单前，要先减少被购买商品的库存。

输入按以下格式通过标准输入给出： > $N$ > $A_1\ A_2\ \dots\ A_N$ > $Q$ > $l_1\ r_1\ k_1$ > $l_2\ r_2\ k_2$ > $\vdots$ > $l_Q\ r_Q\ k_Q$

输出 $Q$ 行。 第 $i$ 行应包含在第 $i$ 个订单中购买的商品总数。

### 样例解释 1 本输入包含 $5$ 个订单。 - 初始时，各商品的库存（从第 $1$ 种商品起）分别为 $2, 6, 4, 5, 7, 5$。 - 第一个订单为 $l_1=1,\ r_1=6,\ k_1=1$。 - 本次订单中，各商品分别购买 $1,1,1,1,1,1$ 件，总共 $6$ 件。 - 之后，商品库存变为 $1,5,3,4,6,4$。 - 第二个订单为 $l_2=3,\ r_2=5,\ k_2=4$。 - 本次订单中，各商品分别购买 $0,0,3,4,4,0$ 件，总共 $11$ 件。 - 之后，商品库存变为 $1,5,0,0,2,4$。 - 第三个订单为 $l_3=4,\ r_3=4,\ k_3=1$。 - 本次订单中，各商品分别购买 $0,0,0,0,0,0$ 件，总共 $0$ 件。 - 之后，商品库存变为 $1,5,0,0,2,4$。 - 第四个订单为 $l_4=2,\ r_4=5,\ k_4=1$。 - 本次订单中，各商品分别购买 $0,1,0,0,1,0$ 件，总共 $2$ 件。 - 之后，商品库存变为 $1,4,0,0,1,4$。 - 第五个订单为 $l_5=1,\ r_5=6,\ k_5=100$。 - 本次订单中，各商品分别购买 $1,4,0,0,1,4$ 件，总共 $10$ 件。 - 之后，商品库存变为 $0,0,0,0,0,0$。 ### 数据范围 - 所有输入值均为整数。 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq A_i \leq 10^{15}$ - $1 \leq Q \leq 3 \times 10^5$ - $1 \leq l_i \leq r_i \leq N$ - $1 \leq k_i \leq 10^9$ 由 ChatGPT 5 翻译