시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 (추가 시간 없음) 1024 MB53360.000%

문제

There are $N+2$ towns in a straight line. The towns are numbered from $0$ through $N+1$ from left to right. Each town $i$ ($1 \leq i \leq N$) has a shelter which can contain up to $A_i$ people.

Currently, $S$ people are traveling together and visiting one of the towns. However, you don't know which town they are visiting.

You just got to know that there are $Q$ meteorites that can hit the towns. The $i$-th meteorite may strike towns $L_i,L_i+1,\cdots,R_i$. To ensure the safety of the travelers, for each meteorite, you want to calculate the evacuation cost.

The evacuation cost for a meteorite is calculated as follows:

  • The evacuation cost is the minimum total cost needed to make all travelers safe no matter which town they are visiting.
  • A person is safe if he/she is in a shelter or a town outside the effect of the meteorite.
  • It takes $1$ unit cost to move one person to an adjacent town (two towns are adjacent iff their numbers differ by exactly $1$).

Note that only moving people costs money, and other actions (like accommodating people in a shelter) don't. It is guaranteed that towns $0$ and $N+1$ will never be affected by meteorites, so it is always possible to make all travelers safe.

Write a program that, for each meteorite, calculates the evacuation cost for that meteorite.

입력

Input is given from Standard Input in the following format:

$N$ $S$

$A_1$ $A_2$ $\cdots$ $A_N$

$Q$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_Q$ $R_Q$

출력

Print $Q$ lines. The $i$-th line should contain the evacuation cost for the meteorite $i$.

제한

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq S \leq 10^{12}$
  • $0 \leq A_i \leq S$
  • $A_1+A_2+\cdots+A_N \leq 10^{12}$
  • $1 \leq Q \leq 2 \times 10^5$
  • $1 \leq L_i \leq R_i \leq N$
  • All values in input are integers.

예제 입력 1

5 10
3 1 1 4 1
3
1 4
3 5
2 5

예제 출력 1

14
10
13

노트

  • For the first meteorite, it takes $14$ unit costs when the travelers are visiting the town $2$.
  • For the second meteorite, it takes $10$ unit costs when the travelers are visiting the town $4$.
  • For the third meteorite, it takes $13$ unit costs when the travelers are visiting the town $3$.