Gleb Evstropov

시간 제한20초메모리 제한512 MB

요약

배열의 원소를 바꾸는 갱신이 섞여 있을 때, 구간 a[l:r)에서 k, k+1, ..., m이 부분수열로 나타나는 가장 큰 m을 구합니다.

문제

배열 $a$ 가 주어집니다.

두 종류의 쿼리를 처리하세요.

$x$ 와 $y$ 가 주어집니다. $a\_x$ 의 값을 $y$ 로 바꿉니다.
$l$ , $r$ , $k$ 가 주어집니다. 수열 $k, k+1, \ldots, m$ 이 $a\_{l:r}$ 의 부분수열이 되도록 하는 가장 큰 $m$ 의 값을 구하세요.

첫 줄에는 두 정수 $n$ 과 $q$ ( $1 \leq n, q \leq 10^6$ )가 주어집니다. 각각 $a$ 의 길이와 쿼리의 개수입니다.

둘째 줄에는 $n$ 개의 정수 $a\_i$ ( $0 \leq a\_i < n$ )가 주어집니다. 이는 $a$ 의 원소입니다.

이어서 $q$ 개의 줄이 주어지며, 각 줄은 다음 중 하나의 형태입니다.

$1 x y$ ( $0 \leq x, y < n$ ): 첫 번째 종류의 쿼리입니다.
$2 l r k$ ( $0 \leq l < r \leq n$ , $0 \leq k < n$ ): 두 번째 종류의 쿼리입니다. 반열린 구간을 쓰므로 $a\_{0:3}$ 은 인덱스 0, 1, 2의 원소를 포함합니다. 주어진 구간에는 $k$ 와 같은 원소가 적어도 하나 있다고 보장됩니다.

두 번째 종류의 각 쿼리에 대해 그에 해당하는 $m$ 을 출력하세요.

예제 1

입력

6 17
0 0 0 1 2 1
2 0 4 0
2 0 5 0
1 3 2
2 0 4 0
2 0 6 0
2 0 4 2
2 5 6 1
1 0 1
2 1 6 1
2 0 5 1
1 0 0
1 5 5
1 2 2
1 4 4
1 3 3
1 1 1
2 0 6 0

예상 출력