406862: GYM102586 B Evacuation
Description
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.
InputInput 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$$$
Constraints:
- $$$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.
Print $$$Q$$$ lines. The $$$i$$$-th line should contain the evacuation cost for the meteorite $$$i$$$.
ExampleInput5 10 3 1 1 4 1 3 1 4 3 5 2 5Output
14 10 13Note
- 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$$$.