Nemmo Nemmo 2020

Mysterious creatures called "nemmo" have started living on an old Tetris board. The board is $10^9$ cells wide and $N$ floors tall, and each nemmo occupies one cell on one floor. For convenience, let $(x, y)$ denote the cell in the $x$-th column from the left and the $y$-th floor from the bottom.

Floor $y$ contains $a_y$ nemmo. Since nemmo like to stay close together, they live side by side in cells $(1, y), \dots, (a_y, y)$, and because they are affected by gravity, $a_y \ge a_{y+1}$ for every $1 \le y \le N - 1$.

Nemmo living on the Tetris board. Here $N = 3$, $a_1 = 3$, $a_2 = 3$, and $a_3 = 2$.

Leff, who wants to play Tetris, plans to clear the nemmo away with a laser. Installing a laser at $(x, y)$ makes all nemmo disappear that live in the $x$-th column from the left on floor $y$ or above, along with all nemmo on floor $y$ to the right of $(x, y)$. No other nemmo disappears right away.

A laser installed at $(1, 2)$. A total of 4 nemmo are hit by the laser and disappear.

There are $Q$ positions where a laser can be installed. For each position, tell Leff how many nemmo would be removed if a laser were installed there. Since this is only planning an installation rather than actually installing lasers, the plans do not affect one another.

The first line contains two integers $N$ and $Q$ separated by a space. $N$ is the height of the board, and $Q$ is the number of positions where a laser can be installed.

The second line contains $N$ integers $a_1, \dots, a_N$ separated by spaces. This means that floor $i$ contains $a_i$ nemmo.

Each of the next $Q$ lines gives a position where a laser can be installed. The $(i + 2)$-th line contains two integers $x_i$ and $y_i$ separated by a space, meaning a laser can be installed at $(x_i, y_i)$.

Print the answers over $Q$ lines. The $i$-th line should contain the number of nemmo removed by installing a laser at $(x_i, y_i)$.

• $1 \le N, Q \le 250{,}000$
• $1 \le a_i \le 10^9$ ($1 \le i \le N$)
• $a_1 \ge a_2 \ge \dots \ge a_N$
• $1 \le x_i \le 10^9$, $1 \le y_i \le n$ ($1 \le i \le Q$)