#515. Nanami and the LLM Training Problem

Nanami 要完成她的毕业论文了。

Nanami 为了训练大语言模型，买了 $n$ 台服务器，这 $n$ 台服务器的编号为 $1,\dots,n$。其中任意的第 $i$ 台至第 $i+1(i<n)$ 台服务器之间都有一根单向的电线连接，用于传输电量。

初始时，每台服务器也都自带电池，电池能提供的电量为 $a_1,\dots,a_n$。同时，Nanami 可以在任意一台服务器上加装提供电量为 $b$ 的电池，该电池提供的电量也可以被电线传输走。

在训练大语言模型的过程中，需要编号连续的一些服务器共同计算，所以这些服务器都需要至少有 $k$ 点电量提供（自己的电池或者是从前一个服务器传输过来的电量）。

Nanami 想问你，在切断第 $l-1$ 至第 $l$ 个服务器之间的电线的前提下 $(l>1)$，如果要使得编号为 $l$ 至 $r$ 的服务器都至少有 $k$ 点电量，她最少需要在编号为 $l$ 的服务器上加装提供电量为多少的电池呢？

第一行，一个整数 $n(1\le n\le 2·10^5)$，代表服务器数量。

接下来的一行有 $n$ 个整数 $a_1,\dots,a_n(1\le a_i\le 10^9)$，代表每台服务器也都自带电池提供的电量。

第三行，一个整数 $q(1\le q\le 2·10^5)$，代表询问次数。

接下来的 $q$ 行，每行三个整数 $l,r,k(1\le l\le r\le n;1\le k\le 10^9)$，代表询问在切断第 $l-1$ 至第 $l$ 个服务器之间的电线的前提下 $(l>1)$，如果要使得编号为 $l$ 至 $r$ 的服务器都至少有 $k$ 点电量，她最少需要在编号为 $l$ 的服务器上加装提供电量为多少的电池？

每个询问都是独立的，也就意味着，Nanami 并不会真正去加装电池，也不会切断服务器之间的连接，原有的电池电量也不会被消耗。

共 $q$ 行，对于每个询问，输出一行整数代表 Nanami 最少需要在编号为 $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