32129번 - 마법 구슬 서브태스크

$N$개의 구역이 일직선으로 놓여 있다. 각 구역은 왼쪽에 있는 구역부터 차례대로 $1, 2, \cdots, N$의 번호가 붙어있으며, $i$번 구역의 초기 가치는 $V_i$이다.

마법 구슬은 구역의 가치를 높여준다. 구슬을 $1$번 구역에 내려놓으면 구슬은 다음과 같이 행동한다.

1. 구슬이 현재 놓여 있는 구역을 $p$번 구역이라고 하자. 만약 $p < N$이고 $p$번 구역의 가치보다 $p+1$번 구역의 가치가 더 낮다면, 구슬은 $p+1$번 구역으로 이동한다. 구슬이 더 이상 이동하지 않을 때까지 이 과정을 반복한다.
2. 구슬이 $p$번 구역에서 더 이상 이동하지 않는다면, 이 구역의 가치에 $1$을 더한다.

마법사는 당신에게 아래 두 가지 종류의 작업을 총 $Q$번 처리하라는 의뢰를 남겼다.

• $1$ $x$ : $1$번 구역에 구슬을 $x$번 내려놓는다. 구슬은 1개씩 내려놓으며, 이전에 내려놓은 구슬의 이동이 멈추고 이동이 멈춘 구역의 가치를 증가시킨 뒤에 새로운 구슬을 내려놓는다.
• $2$ : $1$번 구역의 가치를 출력한다.

당신은 $Q$번의 작업을 차례대로 수행하는 프로그램을 작성해야 한다. 모든 작업의 결과는 누적되며, $1$번 구역의 가치를 출력하는 작업이 한 번 이상 주어진다.

첫째 줄에 $N$, $Q$가 공백으로 구분되어 주어진다.

둘째 줄에 각 구역의 초기 가치 $V_1, V_2, \cdots, V_N$이 공백으로 구분되어 주어진다.

셋째 줄부터 $Q$개의 줄에 마법사의 의뢰가 한 줄에 하나씩 주어진다.

$1$번 구역의 가치를 출력하는 작업의 답을 한 줄에 하나씩 출력하라.

• 주어지는 모든 수는 정수이다.
• $1 \leq N \leq 500\,000$
• $1 \leq Q \leq 500\,000$
• $0 \leq V_{i} \leq 1\,000\,000$ ($1 \le i \le N$)
• $1 \leq x \leq 1\,000\,000$
• $1$번 구역의 가치를 출력하는 작업이 한 번 이상 주어진다.