Longest Subsequence Queries on a Binary Sequence

You are given a binary (0/1) sequence \(a_1,a_2,\dots,a_n\) of length \(n\), and then \(m\) queries. There are two types of queries:

• 1 l r: For the subarray \(a_l, a_{l+1}, \dots, a_r\), compute the length of the longest non-decreasing subsequence.
• 2 l r: For the subarray \(a_l, a_{l+1}, \dots, a_r\), compute the length of the longest strictly increasing subsequence.

Note:

• A subsequence is obtained by deleting zero or more elements (not necessarily contiguous) while keeping the order.
• A sequence \(b_1,b_2,\dots,b_k\) is non-decreasing if \(b_1 \le b_2 \le \cdots \le b_k\); it is strictly increasing if \(b_1 < b_2 < \cdots < b_k\).

Explanation:

For example, if the subarray is [0, 1], the longest non-decreasing subsequence is [0,1] with length 2, and the longest strictly increasing subsequence is also [0,1] of length 2. In contrast, if the subarray is [1, 0], no two elements can form a strictly increasing subsequence (since 0 is not greater than 1), so the answer is 1 for the strictly increasing query; however, for the non-decreasing query, you can take either [1] or [0] (length 1).

Hint for Query Type 1: In a binary sequence, any non-decreasing subsequence can consist of some 0's followed by some 1's. To maximize the length, one strategy is to choose a splitting point \(p\) (with \(p\) from \(l-1\) to \(r\)), taking all 0's occurring in \([l, p]\) and all 1's in \([p+1, r]\). Thus, the answer is
\[ \max\Big\{\#0's,\; \#1's,\; \max_{p=l-1}^{r}\Big((\#\,0's \;in\; [l,p]) + (\#\,1's \;in\; [p+1,r])\Big)\Big\}. \]

Hint for Query Type 2: Because the sequence is binary, a strictly increasing subsequence can only be of the form [0,1] (of length 2) if there exists at least one 0 that occurs before a 1; otherwise, the answer is 1.

inputFormat

The first line contains two integers \(n\) and \(m\) (the length of the sequence and the number of queries).

The second line contains \(n\) space‐separated integers (each either 0 or 1) representing the sequence \(a_1, a_2, \dots, a_n\).

Each of the following \(m\) lines contains a query in one of the following two formats:

• 1 l r
• 2 l r

outputFormat

For each query, output a single integer — the answer to the query on a separate line.

sample

5 4
0 1 0 0 1
1 1 5
2 1 5
2 2 4
1 3 5

4
2
1
3

</p>