G. Nanami and the LLM Training Problem
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nanami buys $$$n$$$ servers, which are numbered $$$1,\dots,n$$$, in order to train a large language model. Any $$$i$$$ server is connected to any $$$i+1$$$ server by a unidirectional wire that transfers power $$$(i \lt n)$$$.

Initially, each server also has its own battery, which provides $$$a_1,\dots,a_n$$$. At the same time, Nanami can add a battery that provides $$$b$$$ of power to any of the servers, and the power provided by this battery can also be transmitted by wires.

In the process of training a large language model, a number of consecutive servers need to be numbered to compute together, so each of these servers needs to have at least $$$k$$$ points of power to provide (either its own battery or power transferred from a previous server).

Nanami wants to ask you, given that the wires between the $$$l-1$$$ and $$$l$$$ servers are cut off $$$(l \gt 1)$$$, what is the minimum number of batteries she needs to add to the $$$l$$$ servers to provide at least $$$k$$$ points of power if she wants to have at least $$$k$$$ points of power available to the $$$l$$$ servers numbered from $$$l$$$ to $$$r$$$?

Input

The first line, an integer $$$n(1\le n\le 2·10^5)$$$, represents the number of servers.

The next line has $$$n$$$ integers $$$a_1,\dots,a_n(1\le a_i\le 10^9)$$$, representing the amount of power provided by the batteries that each server also comes with.

The third line, an integer $$$q(1\le q\le 2·10^5)$$$, represents the number of queries.

The next $$$q$$$ lines, each with three integers $$$l,r,k(1\le l\le r\le n;1\le k\le 10^9)$$$, represent the number of times the query is asked to disconnect the wires between the $$$l-1$$$ and $$$l$$$ servers $$$(l \gt 1)$$$, and if the servers numbered $$$l$$$ through $$$r$$$ are to have at least $$$k$$$ points of power, she will need to add a battery to the servers numbered $$$l$$$ to $$$r$$$ to provide a minimum of $$$k$$$ points of power. What is the minimum number of batteries she needs to add to the server numbered $$$l$$$ to provide power?

Each query is independent, which means that Nanami doesn't actually add batteries, and the original batteries are not consumed.

Output

There are $$$q$$$ lines, and for each query, an integer line is output representing the minimum amount of power that Nanami will need to provide by adding batteries to the server numbered $$$l$$$.

Examples
Input
10
3 5 7 9 8 2 2 1 1 3
7
2 5 10
6 7 1
2 6 2
9 10 7
1 10 7
1 4 10
1 5 7
Output
11
0
0
10
29
16
6
Input
10
12 1 18 7 10 1000000000 999999999 13 25 999999979
10
6 10 18
7 8 500000520
3 7 825490234
4 10 129038019
1 2 3
5 8 377
2 9 7
7 10 438925
1 5 17
2 4 114514
Output
0
1028
2476470667
258076021
0
367
6
0
37
343516