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$$$?
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.
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$$$.
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
11 0 0 10 29 16 6
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
0 1028 2476470667 258076021 0 367 6 0 37 343516
