I. From one to six
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Length of array which can consist only from numbers $$$1, 2, 3, 4, 5, 6$$$ is $$$n$$$.

You are given $$$q$$$ requests of the kind of $$$t$$$, $$$l$$$, $$$r$$$ ($$$l \leq r$$$), where $$$t$$$ is the type of request (1 or 2), $$$l$$$ and $$$r$$$ — are left and right borders of the subline:

If $$$t = 1$$$. sort the subline $$$[l, r]$$$ in non-decreasing order. This type of request does not require a response.

If $$$t = 2$$$. Print the length of the maximum increasing subsequence on the segment $$$[l, r]$$$

Input

The first row consists of 2 integer numbers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) - length of array and number of requests appropriately. The second row consists of $$$n$$$ integer numbers $$$a_i$$$ ($$$1 \leq a_i \leq 6$$$) - elements of array. In each of the following $$$q$$$ rows contain 3 integer numbers divided by space $$$t$$$, $$$l$$$, $$$r$$$ ($$$1 \leq t \leq 2, 1 \leq l \leq r \leq n$$$) - description of given requests.

Output

In response to each request of the second type print a single integer in a separate row - response to given request.

Examples
Input
6 5
3 5 3 5 1 6
1 4 4
2 1 2
2 2 3
2 4 6
1 1 2
Output
2
1
2
Input
6 4
5 2 4 5 1 2
2 3 5
1 2 3
1 3 6
2 3 6
Output
2
4