#829 Coordinate Compression and Queries

Statement

Statement language

You are given an integer array $A = [A_1, A_2, \cdots, A_N]$ of length $N$ .

Coordinate compression of a contiguous subarray is defined as follows. Let $M$ be the number of distinct values in that subarray. Replace each value $x$ in the subarray with the number of distinct values in the same subarray that are strictly smaller than $x$ . Thus, the resulting values lie between $0$ and $M-1$ , inclusive. Elements outside the subarray remain unchanged.

Process the following three types of queries in order.

1 $l$ $r$ : Coordinate-compress the subarray $[l,r]$ .
2 $l$ $r$ : Let $m$ and be the minimum and maximum values in the subarray . Print a value that occurs in this subarray and is closest to . If multiple distinct values are equally close, print the smallest one.

Every query operates on the array after all previous queries have been applied.

Input

The input is given in the following format:

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

Output

For each type 2 query, print the required value on its own line.

Constraints

$1 \leq N \leq 20\,000$ .
$1 \leq Q \leq 20\,000$ .
$∣ A_{i}$ ().

Subtasks

#	Score	Constraints
1	25	$N,Q \leq 5\,000$ .
2	30	$N,Q \leq 10\,000$ .
3	45

Samples

Sample 1

Input

Output

After the first type 1 query, the array becomes $[-3,1,1,0,2]$ . After the second, it becomes $[1,3,3,0,2]$ .