넴모넴모 2020

오래된 테트리스 게임판 위에 수수께끼의 생물 “넴모”들이 살기 시작했다. 이 게임판은 가로로 $10^9$칸, 세로로 $N$층 크기이고, 넴모 한 마리는 한 층의 한 칸을 차지하고 산다. 편의상 왼쪽에서부터 $x$번째, 아래쪽에서부터 $y$층을 $(x, y)$로 표기하자.

$y$층에는 $a_y$마리의 넴모들이 살고 있다. 넴모들은 붙어있는 걸 좋아하기 때문에 $(1, y), \dots, (a_y, y)$ 칸에 나란히 살고 있으며, 중력의 영향을 받기 때문에 모든 $1 \le y \le N - 1$에 대해 $a_y \ge a_{y+1}$이다.

테트리스 게임판에 살고 있는 넴모들. 이 경우 $N = 3$, $a_1 = 3$, $a_2 = 3$, $a_3 = 2$이다.

테트리스를 하고 싶은 레프는 레이저를 이용해서 넴모들을 치워버리려고 한다. $(x, y)$에 레이저를 설치하면 왼쪽에서 $x$번째 칸에 살고 있는 넴모들 중 $y$층 이상에 살고 있는 넴모들, $y$층에 있는 넴모들 중 $(x, y)$보다 오른쪽에 있는 넴모들이 모두 사라진다. 그 이외의 넴모는 당장 사라지지는 않는다.

$(1, 2)$에 레이저를 설치한 모습. 총 4마리의 넴모가 레이저에 맞아 사라진다.

레이저를 설치할 수 있는 위치는 총 $Q$개가 있다. 레프를 위해 각 위치에 레이저를 설치했을 때 몇 마리의 넴모를 없앨 수 있는지 알려주자. 단, 실제로 레이저를 설치하는 것이 아닌 설치 계획만 하는 것이기 때문에, 설치 계획끼리 서로 영향을 주고받지는 않는다.

첫째 줄에 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $N$은 게임판의 세로 크기, $Q$는 레이저를 설치할 수 있는 위치의 수를 의미한다.

둘째 줄에는 $N$개의 정수 $a_1, \dots, a_N$이 공백을 사이에 두고 주어진다. 이는 $i$층에 $a_i$마리의 넴모가 살고 있다는 의미이다.

셋째 줄부터 $Q$개의 줄에 걸쳐 레이저를 설치할 수 있는 위치가 주어진다. $(i + 2)$번째 줄에는 두 정수 $x_i$와 $y_i$가 공백을 사이에 두고 주어지는데, 이는 $(x_i, y_i)$에 레이저를 설치할 수 있다는 의미이다.

$Q$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $(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$)