좌표 압축과 쿼리

길이 $N$인 정수 배열 $A = [A_1, A_2, \cdots, A_N]$이 주어진다.

배열의 연속한 구간에 대한 좌표 압축은 다음과 같이 정의한다. 구간에 등장하는 서로 다른 값의 개수를 $M$이라 하자. 구간의 각 원소 $x$를, 그 구간에 등장하는 서로 다른 값 중 $x$보다 작은 값의 개수로 바꾼다. 따라서 압축된 값은 $0$ 이상 $M-1$ 이하이고, 구간 밖의 원소는 바뀌지 않는다.

다음 세 종류의 쿼리를 순서대로 처리하라.

• 1 $l$ $r$: 구간 $[l,r]$을 좌표 압축한다.
• 2 $l$ $r$: 구간 $[l$의 최솟값을 , 최댓값을 이라 하자. 구간에 실제로 존재하는 값 중 와 가장 가까운 값을 출력한다. 그러한 값이 여러 개이면 가장 작은 값을 출력한다.

각 쿼리는 앞선 모든 쿼리가 적용된 배열을 대상으로 한다.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$

각 2번 쿼리마다 조건을 만족하는 값을 한 줄에 하나씩 출력한다.

• $1 \leq N \leq 20\,000$.
• $1 \leq Q \leq 20\,000$.
• $\mathrm{\mid }{A}_i$ ().