마법 구슬

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

요약

1번 구역에 공을 떨어뜨리면 오른쪽으로 굴러가며 지나온 칸마다 멈춘 곳의 가치를 1 올리고, 1번 구역의 가치를 묻는 질의에 답한다.

문제

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

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

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

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

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

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

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

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

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

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