마법 구슬

시간 제한1초메모리 제한1024 MB

요약

1번 구역에 떨어진 마법 구슬이 낮은 오른쪽 구역으로 굴러가다 멈춘 구역의 값을 1씩 올립니다. 구슬을 여러 번 떨어뜨린 뒤 1번 구역의 값을 묻는 문제입니다.

문제

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

마법 구슬은 구역의 가치를 높인다. 구슬을 $1$ 번 구역에 내려놓으면 구슬은 다음과 같이 움직인다.

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

마법사는 두 종류의 작업을 총 $Q$ 번 순서대로 처리해 달라고 의뢰했다. 모든 작업의 결과는 누적된다. 1번 구역의 가치를 출력하는 작업은 한 번 이상 주어진다.

1 x: 1번 구역에 구슬을 $x$ 개 내려놓는다. 구슬은 하나씩 내려놓는다. 구슬은 이동을 마친 뒤 멈춘 구역의 가치를 올리고, 그다음에 다음 구슬을 내려놓는다.
2: 1번 구역의 가치를 출력한다.

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

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

셋째 줄부터 $Q$ 개의 줄에 작업이 한 줄에 하나씩 주어진다.

종류 2의 작업마다 1번 구역의 가치를 한 줄에 하나씩 출력한다.