There are N (1≤N≤2⋅105) buckets in a stack where the i-th bucket from the top has capacity ai gallons (1≤ai≤109). A tap above the top bucket sends one gallon of milk per second into the first bucket per second. There is also a pool below bucket N.
When a bucket reaches its capacity after t seconds, at the start of the t+1 th second it flips to dump its contents into either the bucket below if it is not the last bucket or the pool otherwise (it reverts back to filling at the end of the t+1th second). A bucket cannot collect milk while it is flipped; any milk arriving at the bucket above during this second is lost. Additionally, any amount of milk exceeding the capacity of the bucket below is lost.
Handle Q (1≤Q≤3⋅105) queries, each specified by three integers i, v, and t:
1.First, set ai =v (1≤i≤N,1≤v≤109).
2.Then answer the following question: Suppose that at time 0, all buckets as well as the pool are empty. Determine the number of gallons of milk in the pool after t seconds (1≤t≤ 1018 ).
The ai=v updates persist through later queries.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The second line contains a1…aN.
The next line contains Q.
Then the following Q lines contain three integers i, v, and t. This means that you should set ai=v and then answer the question for t.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the answer to each question on a separate line.
SAMPLE INPUT:
3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 10
SAMPLE OUTPUT:
0
0
0
1
1
2
2
3
3
4
0
0
0
0
1
1
1
2
2
2
0
0
0
0
1
1
1
2
2
2
When a=[1,1,1],
Bucket 1 flips at times 2,4,6,…
Bucket 2 flips at times 3,5,7,…
Bucket 3 flips at times 4,6,8,…
When a=[2,1,1],
Bucket 1 flips at times 3,6,9,…
Bucket 2 flips at times 4,7,10,…
Bucket 3 flips at times 5,8,11,…
When a=[2,2,1],
Bucket 1 flips at times 3,6,9,…
Bucket 2 flips at times 4,7,10,…
Bucket 3 flips at times 5,8,11,…
SAMPLE INPUT:
2
1 2
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
SAMPLE OUTPUT:
0
0
0
0
2
2
2
2
4
4
SAMPLE INPUT:
3
1 1 1
1
1 1 1000000000000000000
SAMPLE OUTPUT:
499999999999999999
SCORING:
Inputs 4-5: N≤10,Q≤100, and all t≤104
Inputs 6-11: N≤103,Q≤104
Inputs 12-23: No additional constraints.
Problem credits: Akshaj Arora