{"raw_statement":[{"iden":"statement","content":"Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has $N$ ( $1\\le N\\le 2\\cdot 10^5$) haybales sorted in non-increasing order,  where the $i$-th haybale has $a_i$ units of hay ($2\\cdot 10^5\\ge a_1\\ge a_2 \\ge \\dots \\ge a_N \\ge 1$).  \n\nFarmer John is considering splitting a contiguous range of haybales $a_l, \\dots, 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).  \n\nYou are given $Q$ ($1\\le Q\\le 2\\cdot 10^5$) queries, each with three integers $l,r,x$ ($1\\le l\\le r\\le N$, $|x|\\le 10^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."},{"iden":"input","content":"First line contains $N$.  \n\nSecond line contains $a_1\\dots a_N$.  \n\nThird line contains $Q$.  \n\nNext $Q$ lines contain $l, r, x$."},{"iden":"output","content":"Output $Q$ lines, containing the answer for each query."},{"iden":"note","content":"##### For Sample 1:\nFor 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.   \n\nFor 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.  \n\nFor 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. \n##### For Sample 2:\nIn 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.  \n\n#### SCORING:\n- Input 3: $Q\\le 100$.\n- Inputs 4-6: At most $100$ distinct $a_i$.\n- Inputs 7-22: No additional constraints."}],"translated_statement":null,"sample_group":[["2\n3 1\n15\n1 1 -2\n1 1 -1\n1 1 0\n1 1 1\n1 1 2\n1 2 -2\n1 2 -1\n1 2 0\n1 2 1\n1 2 2\n2 2 -2\n2 2 -1\n2 2 0\n2 2 1\n2 2 2","1\n2\n3\n-2\n-1\n0\n1\n2\n-1\n0\n-1\n0\n1\n0\n1"],["5\n4 4 3 1 1\n7\n1 1 20\n1 2 20\n1 5 20\n1 1 0\n1 5 0\n1 4 0\n3 5 2","16\n12\n7\n4\n1\n2\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}