Page not loading? Try clicking here.
Placeholder

#8175
Subtask

Splitting Haybales 1s 1024MB

Problems

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.


Input

First line contains N.

Second line contains a_1\dots a_N.

Third line contains Q.

Next Q lines contain l, r, x.


Output

Output Q lines, containing the answer for each query.


Subtask

# Score Condition
#120

Q \le 100

#230

At most 100 distinct a_i

#350

추가 제약 조건 없음


Example #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
1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1

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.


Example #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
16
12
7
4
1
2
1

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.


Source

USACO 2024 US Open Platinum

You must sign in to write code.