|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|6 초 (추가 시간 없음)||1024 MB||3||2||2||66.667%|
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:
$A_1$ $A_2$ $\cdots$ $A_N$
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