만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

건초 더미 나누기

시간 제한2초메모리 제한1024 MB

요약
정렬된 건초더미를 l번째부터 r번째까지 건초가 적은 소에게 차례로 줄 때, 시작 차이 x에서 끝나는 차이를 구합니다.
난이도

어려움10점 중 8점

유형
배열, 분할 정복, 누적 합
정답자
아직 제출이 없습니다

문제

Farmer John은 좋아하는 두 마리의 소 Bessie와 Elsie에게 건초 더미를 공평하게 나누려고 합니다. 그는 내림차순으로 정렬된 건초 더미 NN개(1≤N≤2⋅1051\le N\le 2\cdot 10^5)를 가지고 있으며, ii번째 더미에는 aia_i단위의 건초가 있습니다(2⋅105≥a1≥a2≥⋯≥aN≥12\cdot 10^5\ge a_1\ge a_2\ge \dots \ge a_N\ge 1).

Farmer John은 연속한 구간의 더미 al,…,ara_l, \dots, a_r을 Bessie와 Elsie에게 나눕니다. 더미를 ll번째부터 rr번째까지 순서대로 처리하며, 각 더미는 건초가 더 적은 소에게 줍니다. 두 소의 건초량이 같으면 Bessie에게 줍니다.

QQ개의 쿼리(1≤Q≤2⋅1051\le Q\le 2\cdot 10^5)가 주어지며, 각 쿼리는 정수 ll, rr, xx(1≤l≤r≤N1\le l\le r\le N, ∣x∣≤109|x|\le 10^9)로 이루어집니다. 각 쿼리에서 Bessie는 처음에 Elsie보다 xx단위 더 많은 건초를 가지고 있습니다. 더미 ll번째부터 rr번째까지 처리한 뒤 Bessie가 Elsie보다 몇 단위 더 많은 건초를 가지는지 구합니다. Elsie가 더 많이 가지면 이 값은 음수입니다.

입력

첫 줄에 NN이 주어집니다.

둘째 줄에 a1…aNa_1\dots a_N이 주어집니다.

셋째 줄에 QQ가 주어집니다.

다음 QQ개의 줄에 각각 ll, rr, xx가 주어집니다.

출력

QQ줄을 출력합니다. jj번째 줄에는 jj번째 쿼리의 답을 출력합니다.

예제2

  1. 예제 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

  2. 예제 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