F - Clearance Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

AtCoder 社のオンラインショップでは現在 N 個の商品を取り扱っており、商品 i の在庫は残り A_i 個です。

以下の Q 件の注文を順に処理してください。そのうち i 件目は次の通りです。

  • 商品 l_i,l_i+1,\dots,r_i を k_i 個ずつ買う。但し、 k_i 個未満の商品はあるだけ全て買う。この注文で買われた商品の個数の合計を答えよ。

i<Q について、 i 件目の注文で買われた商品の在庫を減らした状態で i+1 件目の注文に進むことに注意してください。

制約

  • 入力は全て整数
  • 1 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^{15}
  • 1 \le Q \le 3 \times 10^5
  • 1 \le l_i \le r_i \le N
  • 1 \le k_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

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

6
2 6 4 5 7 5
5
1 6 1
3 5 4
4 4 1
2 5 1
1 6 100

出力例 1

6
11
0
2
10

この入力には 5 件の注文が含まれます。

  • はじめ、各商品の在庫は (商品 1 から順に) 2,6,4,5,7,5 個です。
  • 1 件目の注文は l_1 = 1, r_1 = 6, k_1 = 1 です。
    • この注文で各商品は 1,1,1,1,1,1 個、合計 6 個買われます。
    • その後、各商品の在庫は 1,5,3,4,6,4 個になります。
  • 2 件目の注文は l_2 = 3, r_2 = 5, k_2 = 4 です。
    • この注文で各商品は 0,0,3,4,4,0 個、合計 11 個買われます。
    • その後、各商品の在庫は 1,5,0,0,2,4 個になります。
  • 3 件目の注文は l_3 = 4, r_3 = 4, k_3 = 1 です。
    • この注文で各商品は 0,0,0,0,0,0 個、合計 0 個買われます。
    • その後、各商品の在庫は 1,5,0,0,2,4 個になります。
  • 4 件目の注文は l_4 = 2, r_4 = 5, k_4 = 1 です。
    • この注文で各商品は 0,1,0,0,1,0 個、合計 2 個買われます。
    • その後、各商品の在庫は 1,4,0,0,1,4 個になります。
  • 5 件目の注文は l_5 = 1, r_5 = 6, k_5 = 100 です。
    • この注文で各商品は 1,4,0,0,1,4 個、合計 10 個買われます。
    • その後、各商品の在庫は 0,0,0,0,0,0 個になります。

Score : 525 points

Problem Statement

AtCoder Inc.'s online shop currently handles N products, and the stock of product i is A_i units remaining.

Process the following Q orders in order. The i-th order is as follows:

  • Buy k_i units each of products l_i,l_i+1,\dots,r_i. For products with fewer than k_i units, buy all available units. Report the total number of products bought in this order.

Note that for i<Q, the stock of products bought in the i-th order is reduced before proceeding to the (i+1)-th order.

Constraints

  • All input values are integers.
  • 1 \le N \le 3 \times 10^5
  • 1 \le A_i \le 10^{15}
  • 1 \le Q \le 3 \times 10^5
  • 1 \le l_i \le r_i \le N
  • 1 \le k_i \le 10^9

Input

The input is given from Standard Input in the following format:

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

Output

Output Q lines.
The i-th line should contain the total number of products bought in the i-th order.

Sample Input 1

6
2 6 4 5 7 5
5
1 6 1
3 5 4
4 4 1
2 5 1
1 6 100

Sample Output 1

6
11
0
2
10

This input contains 5 orders.

  • Initially, the stocks of the products are (from product 1 onward) 2,6,4,5,7,5 units.
  • The first order is l_1 = 1, r_1 = 6, k_1 = 1.
    • In this order, 1,1,1,1,1,1 units of the products are bought, for a total of 6 units.
    • After this, the stocks of the products become 1,5,3,4,6,4 units.
  • The second order is l_2 = 3, r_2 = 5, k_2 = 4.
    • In this order, 0,0,3,4,4,0 units of the products are bought, for a total of 11 units.
    • After this, the stocks of the products become 1,5,0,0,2,4 units.
  • The third order is l_3 = 4, r_3 = 4, k_3 = 1.
    • In this order, 0,0,0,0,0,0 units of the products are bought, for a total of 0 units.
    • After this, the stocks of the products become 1,5,0,0,2,4 units.
  • The fourth order is l_4 = 2, r_4 = 5, k_4 = 1.
    • In this order, 0,1,0,0,1,0 units of the products are bought, for a total of 2 units.
    • After this, the stocks of the products become 1,4,0,0,1,4 units.
  • The fifth order is l_5 = 1, r_5 = 6, k_5 = 100.
    • In this order, 1,4,0,0,1,4 units of the products are bought, for a total of 10 units.
    • After this, the stocks of the products become 0,0,0,0,0,0 units.