Splitting Haybales

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$).

Farmer 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).

You 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.

First line contains $N$.

Second line contains $a_1\dots a_N$.

Third line contains $Q$.

Next $Q$ lines contain $l, r, x$.

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