리스트 가상화

한국정보기술진흥원에서 새로 개발한 모바일 어플리케이션의 화면에는 $N$개의 직사각형 항목이 빈틈없이 세로로 나열되어 있다. 위에서 $i$번째 항목의 높이는 $H_i$이다. 가장 위에 있는 항목의 위쪽 변은 화면의 맨 위와 맞닿아 있다. 사용자의 요청 $Q$개를 순서대로 처리해야 한다. 어떤 요청에서도 요청 전에 있던 항목들의 순서가 요청 후에 뒤바뀌지 않는다.

• 1 $i$ $h$: 높이가 $h$인 새 직사각형 항목을 위에서 $i$번째에 끼워 넣는다. $j \lt i$인 모든 $j$에 대해 새 항목은 위에서 $j$번째 항목보다 아래에 있게 된다. $j \ge i$인 항목은 끼워 넣기 전에 위에서 $j$번째였던 항목으로, 새 항목보다 아래로 내려간다. 움직인 뒤에도 모든 항목은 빈틈없이 나열되어야 한다.
• 2 $i$: 위에서 $i$번째 항목을 지운다. $j \gt i$인 항목은 지우기 전에 위에서 $j$번째였던 항목으로, 모든 항목이 빈틈없이 나열되도록 위로 움직인다.
• 3 $t$ $b$: 화면 맨 위에서 $t$만큼 떨어진 위치부터 $b$만큼 떨어진 위치까지의 범위에, 직사각형 경계를 제외한 내부의 점이 하나 이상 포함되는 항목의 수를 구한다.

첫 줄에는 처음 화면에 있는 항목의 수 $N$과 요청의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$

둘째 줄에는 각 항목의 높이 $H_1, H_2, \cdots, H_N$이 공백으로 구분되어 주어진다. $(1 \le H_i \le 1\,000\,000\,000)$

셋째 줄부터 $Q$개의 줄에 걸쳐 요청이 주어진다. 요청은 다음 형식 중 하나를 따른다.

• 1 $i$ $h$ $(1 \le i \le$ (요청 직전에 존재하는 항목의 수) $+ 1$, $1 \le h \le 1\,000\,000\,000)$
• 2 $i$ $(1 \le i \le$ (요청 직전에 존재하는 항목의 수)$)$
• 3 $t$ $b$ $(0 \le t \lt b \le 400\,000\,000\,000\,000)$

3 $t$ $b$ 요청이 들어올 때마다, 화면 맨 위에서 $t$만큼 떨어진 위치부터 $b$만큼 떨어진 위치까지의 범위에 직사각형 경계를 제외한 내부의 점이 하나 이상 포함되는 항목의 수를 한 줄에 출력한다.