Splitting Haybales

문제

Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has $NN$ ( $1\le N\le 2\cdot {10}^{5}1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5$) haybales sorted in non-increasing order, where the $ii$-th haybale has $a_{i}a\_i$ units of hay ($2\cdot {10}^5\ge a_1\ge a_2\ge \cdots \ge a_N\ge 12\backslash cdot\; 10^5\backslash ge\; a\_1\backslash ge\; a\_2\; \backslash ge\; \backslash dots\; \backslash ge\; a\_N\; \backslash ge\; 1$).

Farmer John is considering splitting a contiguous range of haybales $a_l,\dots ,a_{r}a\_l,\; \backslash dots,\; a\_r$ between Bessie and Elsie. He has decided to process the haybales in order from $ll$ to $rr$, and when processing the $ii$-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 $QQ$ ($1\le Q\le 2\cdot {10}^{5}1\backslash le\; Q\backslash le\; 2\backslash cdot\; 10^5$) queries, each with three integers $l,r,xl,r,x$ ($1\le l\le r\le N1\backslash le\; l\backslash le\; r\backslash le\; N$, $\mathrm{\mid }x\mathrm{\mid }\le {10}^9|x|\backslash le\; 10^9$). For each query, output how many more units of hay Bessie will have than Elsie after processing haybales $ll$ to $rr$, if Bessie starts with $xx$ more units than Elsie. Note that this value is negative if Elsie ends up with more haybales than Bessie.

입력

First line contains $NN$.

Second line contains $a_1\dots a_{N}a\_1\backslash dots\; a\_N$.

Third line contains $QQ$.

Next $QQ$ lines contain $l,r,xl,\; r,\; x$.

출력

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

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

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

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

16
12
7
4
1
2
1