Problem Description

Farmer John wants to fairly distribute his haybales among his two favorite cows, Bessie and Elsie. He has $N$ ($1 \le N \le 2 \cdot 10^5$) haybales sorted in descending order, where the $i$-th haybale has $a_i$ units of hay ($2 \cdot 10^5 \ge a_1 \ge a_2 \ge \cdots \ge a_N \ge 1$).

Farmer John is considering assigning a continuous interval of haybales $a_l, \ldots, a_r$ to Bessie and Elsie. He decides to process the haybales from $l$ to $r$ in order, and when processing the $i$-th haybale, he will give it to the cow with fewer hay units at that moment (if tied, he will give it to Bessie).

Given $Q$ ($1 \le Q \le 2 \cdot 10^5$) queries, each containing three integers $l, r, x$ ($1 \le l \le r \le N$, $|x| \le 10^9$). For each query, output how many units of hay Bessie will have more than Elsie after processing the haybales from $l$ to $r$, assuming Bessie starts with $x$ units more hay than Elsie. Note that if Elsie ends up with more hay than Bessie, the value will be negative.

Input Format

The first line of input contains $N$.

The second line contains $a_1 \ldots a_N$.

The third line contains $Q$.

The following $Q$ lines contain $l, r, x$.

Output Format

Output $Q$ lines, each containing the answer to a query.

Sample Input and Output

Input Sample #1

2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2

Output Sample #1

1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1

Input Sample #2

5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 2

Output Sample #2

16
12
7
4
1
2
1

Notes/Hints

Sample Explanation 1

For the 1st query, Elsie starts with 2 units more hay than Bessie. After processing haybale 1, Bessie receives 3 units of hay, making Bessie have 1 unit more hay than Elsie.

For the 3rd query, Elsie and Bessie start with the same amount of hay. After processing haybale 1, Bessie receives 3 units of hay, making Bessie have 3 units more hay than Elsie.

For the 9th query, Bessie starts with 1 unit more hay than Elsie. After processing haybale 1, Bessie has 2 units less hay than Elsie, and after processing haybale 2, Bessie has 1 unit less hay than Elsie.

Sample Explanation 2

For the 5th query, there are 5 haybales to process. Bessie receives 4 units of hay, then Elsie receives 4 units of hay, then Bessie receives 3 units of hay, then Elsie receives 1 unit of hay, and finally Elsie receives 1 unit of hay.

Test Case Properties

• Test case $3$: $Q \le 100$.
• Test cases $4-6$: At most $100$ different values of $a_i$.
• Test cases $7-22$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分