有一款极其困难的视频游戏,是 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$$$。
请注意,每个问题都是独立的,因此 Chaneka 对某个问题所做的尝试不会影响任何其他问题的熟悉度值。
输入
第一行包含一个整数 $$$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$$$ 问题。
输出
输出 $$$q$$$ 行,每行一个整数。第 $$$j$$$ 行中的整数表示 Chaneka 使每个部分 $$$p$$$ ($$$l_j \leq p \leq r_j$$$) 的熟悉度值至少为 $$$x_j$$$ 的最短时间(以秒为单位)。
示例
输入 #1
5 1 3 2 1 2 3 1 5 5 2 4 5 3 3 1
输出 #1
15 11 0
注意
对于 $$$1$$$-st 问题,一种可能的策略是执行以下操作:
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$$$-nd 问题,一种可能的策略是执行以下操作:
1. 进行 $$$1$$$ 尝试,结果在 $$$3$$$ 部分死亡。这需要 $$$3$$$ 秒。熟悉度值变为 $$$[2, 4, 4, 1, 2]$$$。
2. 进行 $$$2$$$ 尝试,但在 $$$4$$$ 部分失败。这需要 $$$8$$$ 秒。熟悉度值变为 $$$[4, 6, 6, 5, 2]$$$。
花费的总时间(以秒为单位)为$$$3+8=11$$$。