19845번 - 넴모넴모 2020

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

y층에는 a_y마리의 넴모들이 살고 있다. 넴모들은 붙어있는 걸 좋아하기 때문에 (1, y), …, (a_y, y) 칸에 나란히 살고 있으며, 중력의 영향을 받기 때문에 모든 1 ≤ y ≤ N − 1에 대해 a_y ≥ a_y+1이다.

테트리스 게임판에 살고 있는 넴모들. 이 경우 N = 3, a₁ = 3, a₂ = 3, a₃ = 2이다.

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

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

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

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

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

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

Q개의 줄에 걸쳐 답을 출력한다. i번째 줄에는 (x_i, y_i)에 레이저를 설치하면 몇 마리의 넴모를 제거할 수 있는지 출력한다.

• 1 ≤ N, Q ≤ 250,000
• 1 ≤ a_i ≤ 10⁹ (1 ≤ i ≤ N)
• a₁ ≥ a₂ ≥ … ≥ a_N
• 1 ≤ x_i ≤ 10⁹, 1 ≤ y_i ≤ n (1 ≤ i ≤ Q)