시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 (추가 시간 없음) | 1024 MB | 5 | 3 | 3 | 60.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:
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$.
5 10 3 1 1 4 1 3 1 4 3 5 2 5
14 10 13