Description

You are given a $01$ sequence $a_{1\sim n}$ of length $n$. Then there are $m$ queries of two types:

• 1 l r: query the length of the longest non-decreasing subsequence in the interval from $l$ to $r$.
• 2 l r: query the length of the longest increasing subsequence in the interval from $l$ to $r$.

Input Format

The input contains $m+2$ lines.
Line $1$ contains two positive integers $n, m$.
Line $2$ contains $n$ numbers $0$ or $1$, representing the sequence $a_{1\sim n}$.
The next $m$ lines each contain three positive integers describing one query, in the format above.

Output Format

Output $m$ lines.
For each query, compute the answer and output it.

8 4
0 1 1 0 1 0 0 1
1 1 8
2 1 8
1 3 6
2 5 6

5
2
2
1

Hint

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le n\le 10^6$, $1\le m\le 5\times10^6$, and $0\le a_i\le 1$.

The input and output size is extremely large, so please use fast I/O methods.

Sample Explanation:

For the first query, valid sequences include $\{0,1,1,1,1\}$ and $\{0,0,0,0,1\}$.
For the second query, valid sequences include $\{0,1\}$.
For the third query, valid sequences include $\{0,0\}$, $\{0,1\}$, and $\{1,1\}$.
For the fourth query, valid sequences include $\{0\}$ and $\{1\}$.

$\text{Upd 2021.8.16}$: Added two sets of hack testdata.

Translated by ChatGPT 5