전투 시뮬레이션

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

Cube219는 $Q$번의 전투 시뮬레이션을 하려 한다. $i$번째 전투에서는 $l_i$번째부터 $r_i$번째까지 연속된 구간을 고르고, 이 구간을 $[l_i, \cdots, k]$와 $[k+1, \cdots, r_i]$라는 연속된 두 팀으로 나눈다. 팀의 전투력은 팀에 속한 병사들의 전투력 합으로 정해진다.

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

첫 번째 줄에 구간의 길이 $N$이 주어진다. ($3 \leq N \leq 300000$)

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

세 번째 줄에 전투 시뮬레이션 횟수 $Q$가 주어진다. ($1 \leq Q \leq 300000$)

네 번째 줄부터 $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$개의 줄에 각 전투 시뮬레이션의 답, 즉 두 팀 전투력 차이의 최솟값을 한 줄에 하나씩 출력한다.