CF1876G.Clubstep

There is an extremely hard video game that is one of Chaneka's favourite video games. One of the hardest levels in the game is called Clubstep. Clubstep consists of $n$ parts, numbered from $1$ to $n$. Chaneka has practised the level a good amount, so currently, her familiarity value with each part $i$ is $a_i$.

After this, Chaneka can do several (possibly zero) attempts on Clubstep. In each attempt, she dies on one of the $n$ parts. If an attempt dies on part $p$, that means it only successfully passes through every part $k$ for all $1 \leq k \leq p-1$ and it does not reach any part $k$ for all $p+1 \leq k \leq n$. An attempt that dies on part $p$ takes $p$ seconds.

It is known that Chaneka improves much more on the part she dies on than anything else. It is also known that during an attempt, Chaneka does not get to practise that much on the parts she does not reach. So, the effect of an attempt that dies on part $p$ is as follows:

• Chaneka's familiarity value with part $p$ increases by $2$.
• Chaneka's familiarity value with each part $k$ for all $1 \leq k \leq p-1$ increases by $1$.

There will be $q$ questions. For the $j$-th question, you are given three integers $l_j$, $r_j$, and $x_j$. Then, you are asked to find out the minimum time (in seconds) for Chaneka to make it such that the familiarity value for every part $p$ ($l_j \leq p \leq r_j$) is at least $x_j$.

Note that each question is independent, so the attempt Chaneka does on a question does not affect the familiarity values of any other questions.

有一款极其困难的电子游戏，是Chaneka最喜爱的电子游戏之一。游戏中最难的关卡之一名为“Clubstep”。Clubstep由 $n$ 个部分组成，编号从 $1$ 到 $n$。Chaneka 已经对该关卡进行了大量练习，因此目前她对每个部分 $i$ 的熟悉度值为 $a_i$。

此后，Chaneka 可以进行若干次（可能为零次）Clubstep 尝试。在每次尝试中，她会在 $n$ 个部分中的某一个部分失败。若一次尝试在第 $p$ 部分失败，则意味着该尝试成功通过了所有满足 $1 \leq k \leq p-1$ 的部分 $k$，但未能到达任何满足 $p+1 \leq k \leq n$ 的部分 $k$。在第 $p$ 部分失败的一次尝试耗时 $p$ 秒。

已知 Chaneka 在她失败的部分所获得的进步远超其他任何部分；同时也已知，在一次尝试过程中，她对未能到达的部分几乎无法进行有效练习。因此，在第 $p$ 部分失败的一次尝试会产生如下效果：

• Chaneka 对第 $p$ 部分的熟悉度值增加 $2$；
• Chaneka 对每个满足 $1 \leq k \leq p-1$ 的部分 $k$ 的熟悉度值各增加 $1$。

接下来会有 $q$ 个询问。对于第 $j$ 个询问，给出三个整数 $l_j$、$r_j$ 和 $x_j$。你需要求出：使得所有满足 $l_j \leq p \leq r_j$ 的部分 $p$ 的熟悉度值均至少达到 $x_j$ 所需的最少时间（单位：秒）。

注意：每个询问相互独立，即 Chaneka 在某个询问中进行的尝试不会影响其他询问中的熟悉度值。

The first line contains a single integer $n$ ($1 \leq n \leq 3\cdot10^5$) — the number of parts in Clubstep.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1\leq a_i\leq10^9$) — Chaneka's familiarity value with each part.

The third line contains a single integer $q$ ($1\leq q\leq3\cdot10^5$) — the number of questions.

The $j$-th of the next $q$ lines contains three integers $l_j$, $r_j$, and $x_j$ ($1\leq l_j\leq r_j\leq n$; $1\leq x_j\leq10^9$) — the description of the $j$-th question.

第一行包含一个整数 $n$（$1 \leq n \leq 3\cdot10^5$）—— Clubstep 的部分数量。

第二行包含 $n$ 个整数 $a_1,a_2,a_3,\ldots,a_n$（$1\leq a_i\leq10^9$）—— Chaneka 对每个部分的熟悉度值。

第三行包含一个整数 $q$（$1\leq q\leq3\cdot10^5$）—— 问题的数量。

接下来的 $q$ 行中，第 $j$ 行包含三个整数 $l_j$、$r_j$ 和 $x_j$（$1\leq l_j\leq r_j\leq n$；$1\leq x_j\leq10^9$）—— 第 $j$ 个问题的描述。

Output $q$ lines with an integer in each line. The integer in the $j$-th line represents the minimum time (in seconds) for Chaneka to make it such that the familiarity value for every part $p$ ($l_j \leq p \leq r_j$) is at least $x_j$.

输出 $q$ 行，每行一个整数。第 $j$ 行的整数表示 Chaneka 所需的最少时间（单位：秒），使得每个部分 $p$（其中 $l_j \leq p \leq r_j$）的熟悉度值均至少为 $x_j$。

For the $1$-st question, one possible strategy is to do the following:

1. Do $1$ attempt that dies on part $1$. This takes $1$ second. The familiarity values become $[3, 3, 2, 1, 2]$.
2. Do $1$ attempt that dies on part $4$. This takes $4$ seconds. The familiarity values become $[4, 4, 3, 3, 2]$.
3. Do $2$ attempts that die on part $5$. This takes $10$ seconds. The familiarity values become $[6, 6, 5, 5, 6]$.

The total time taken (in seconds) is $1+4+10=15$.

For the $2$-nd question, one possible strategy is to do the following:

1. Do $1$ attempt that dies on part $3$. This takes $3$ seconds. The familiarity values become $[2, 4, 4, 1, 2]$.
2. Do $2$ attempts that die on part $4$. This takes $8$ seconds. The familiarity values become $[4, 6, 6, 5, 2]$.

The total time taken (in seconds) is $3+8=11$.

对于第 $1$ 个问题，一种可能的策略如下：

1. 执行 $1$ 次在第 $1$ 部分失败的尝试。耗时 $1$ 秒。熟悉度值变为 $[3, 3, 2, 1, 2]$。
2. 执行 $1$ 次在第 $4$ 部分失败的尝试。耗时 $4$ 秒。熟悉度值变为 $[4, 4, 3, 3, 2]$。
3. 执行 $2$ 次在第 $5$ 部分失败的尝试。耗时 $10$ 秒。熟悉度值变为 $[6, 6, 5, 5, 6]$。

总耗时（单位：秒）为 $1+4+10=15$。

对于第 $2$ 个问题，一种可能的策略如下：

1. 执行 $1$ 次在第 $3$ 部分失败的尝试。耗时 $3$ 秒。熟悉度值变为 $[2, 4, 4, 1, 2]$。
2. 执行 $2$ 次在第 $4$ 部分失败的尝试。耗时 $8$ 秒。熟悉度值变为 $[4, 6, 6, 5, 2]$。

总耗时（单位：秒）为 $3+8=11$。