当前没有测试数据。

一、Problem Name

Splitting Haybales

二、Problem Description

Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has $N$ ($1\leq N\leq2\cdot10^5$) haybales sorted in non-increasing order, where the $i$th haybale has $a_i$ units of hay ($2\cdot10^5\geq a_1\geq a_2\geq\cdots\geq a_N\geq1$).

Farmer John is considering splitting a contiguous range of haybales $a_l,\cdots,a_r$ between Bessie and Elsie. He has decided to process the haybales in order from $l$ to $r$, and when processing the $i$th haybale he will give it to the cow who currently has less hay (if it is a tie, he will give it to Bessie).

You are given $Q$ ($1\leq Q\leq2\cdot10^5$) queries, each with three integers $l,r,x$ ($1\leq l\leq r\leq N$, $\vert x\vert\leq10^9$). For each query, output how many more units of hay Bessie will have than Elsie after processing haybales $l$ to $r$, if Bessie starts with $x$ more units than Elsie. Note that this value is negative if Elsie ends up with more haybales than Bessie.

三、Input Format (input arrives from the terminal / stdin)

1. First line contains $N$.
2. Second line contains $a_1\cdots a_N$.
3. Third line contains $Q$.
4. Next $Q$ lines contain $l,r,x$.

四、Output Format (print output to the terminal / stdout)

Output $Q$ lines, containing the answer for each query.

五、Sample Input and Output

Sample Input 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

Sample Output 1

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

Explanation: For the 1st query, Elsie starts with 2 more hay than Bessie. Then, after processing haybale 1, Bessie will receive 3 hay, and Bessie will have 1 more hay than Elsie. For the 3rd query, Elsie and Bessie start with the same number of hay. After processing haybale 1, Bessie will receive 3 hay, and Bessie will have 3 more hay than Elsie. For the 9th query, Bessie starts with 1 more hay than Elsie, then after processing the 1st haybale, has 2 less hay than Elsie, and after processing the 2nd haybale, has 1 less hay than Elsie.

Sample Input 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

Sample Output 2

16
12
7
4
1
2
1

Explanation: In the 5th query, there are 5 haybales to process. Bessie receives 4 hay, then Elsie receives 4 hay, then Bessie receives 3 hay, then Elsie receives 1 hay, then Elsie receives 1 hay.

六、Scoring Rules

1. Input 3: $Q\leq100$.
2. Inputs 4 - 6: At most 100 distinct $a_i$.
3. Inputs 7 - 22: No additional constraints.

Problem credits: Benjamin Qi.