25913번 - 전투 시뮬레이션

문제

Cube219는 전투 시뮬레이션 게임을 즐겨한다. 이 게임에는 길이가 $N$인 공간에 일렬로 1ドル$번부터 $N$번까지 순서대로 병사들이 있다. $i$번째 병사는 $a_i$의 전투력을 가지고 있다. 전투력은 음수가 될 수도 있다.

Cube219는 $Q$번의 전투 시뮬레이션을 하려 한다. $i$번째 전투에는 $l_i$번째부터 $r_i$번째까지 연속된 구간을 선택하고, 이 구간을 $[l_i,\cdots,k], [k+1,\cdots,r_i]$ 인 연속된 2ドル$개의 그룹으로 팀을 나누어 전투를 하려 한다. 팀의 전투력은 팀에 속한 병사들의 전투력의 합으로 결정된다.

Cube219는 전투가 치열하게 일어나는 것을 좋아해서, 두 그룹의 전투력 차이를 최소화하게 팀을 나누려고 한다. 다만 병사의 수가 너무 차이나는 것도 싫어서, 한 그룹의 크기가 전체 전투 구간의 $\dfrac{2}{3}$를 넘지 않도록 하려 한다. 위 조건을 만족하면서, 각 전투 시뮬레이션마다 팀의 전투력 차이의 최솟값을 구하시오.

입력

첫 번째 줄에 구간의 길이 $N$이 정수로 주어진다. $(3 \leq N \leq 300,000円)$

두 번째 줄에 $N$개의 정수 $a_1,\cdots,a_N$이 공백으로 구분되어 주어진다. $(-10^9 \leq a_i \leq 10^9)$ $a_i$는 $i$번째 병사의 전투력이다.

세 번째 줄에 전투 시뮬레이션 횟수 $Q$가 정수로 주어진다. $(1 \leq Q \leq 300,000円)$

네 번째 줄부터는 $Q$개의 줄에 걸쳐 정수 $l_i, r_i$가 공백으로 구분되어 주어진다. $(1 \leq l_i < r_i \leq N;$ $r_i-l_i+1$은 3ドル$의 배수$)$ $l_i, r_i$는 $i$번째 전투 시뮬레이션 구간의 왼쪽 끝과 오른쪽 끝 위치이다.

출력

$Q$개의 줄에 각 전투 시뮬레이션마다 팀의 전투력 차이의 최솟값을 출력한다.

제한

힌트