2025_1D. Simple Subsequence
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We call an array of integers $$$d_1, d_2, \ldots, d_m$$$ good if its length is equal to $$$0$$$, or for any $$$1\le i\le m$$$, both values $$$\sum\limits_{j=1}^{i} d_j$$$ and $$$\sum\limits_{j=i}^{m} d_j$$$ are non-negative. Here, $$$\sum\limits_{j=l}^{r} d_j$$$ denotes $$$d_l+d_{l+1}+\ldots+d_{r}$$$.

We define the beauty of the array as the length of its longest good subsequence$$$^1$$$.

You are given an array $$$a$$$ of length $$$n$$$, which consists of numbers $$$-1$$$ and $$$1$$$.

You need to perform $$$q$$$ queries. The queries are of two types:

  1. replace the element $$$a_p$$$ with $$$-a_p$$$, where $$$p$$$ — the parameter of the query;
  2. find the beauty of the array consisting of elements $$$[a_{l},a_{l+1},\ldots,a_r]$$$, where $$$(l, r)$$$ — the parameters of the query.
Input

In the first line, two integers $$$n$$$, $$$q$$$ are given $$$(1\le n, q\le 5 \cdot 10^5)$$$ — the length of the array $$$a$$$ and the number of queries, respectively.

In the second line, $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(a_i \in \{-1, 1\})$$$ are given — the elements of the array $$$a$$$.

In the next $$$q$$$ lines, the description of the queries is given. The first of the numbers $$$type_i$$$ $$$(1 \le type_i \le 2)$$$ denotes the type of the query. Queries of the first type are given in the format "1 p" $$$(1 \le p \le n)$$$, and queries of the second type are given in the format "2 l r" $$$(1 \le l \le r \le n)$$$.

Output

For each query of the second type, output one integer in a separate line — the beauty of the corresponding array.

Scoring
  1. ($$$2$$$ points): $$$a_i = (-1)^{i+1}$$$ for $$$1 \le i \le n$$$, and there are no type one queries;
  2. ($$$7$$$ points): $$$n \le 16$$$, and there are no type one queries;
  3. ($$$21$$$ points): $$$n, q \le 100$$$;
  4. ($$$20$$$ points): $$$n, q \le 3000$$$;
  5. ($$$27$$$ points): $$$n, q \leq 2 \cdot 10^5$$$, and there are no type one queries;
  6. ($$$14$$$ points): $$$n, q \leq 2 \cdot 10^5$$$;
  7. ($$$9$$$ points): no additional restrictions.
Examples
Input
5 4
1 1 1 -1 1
2 1 5
1 3
2 1 4
2 2 5
Output
5
2
3
Input
4 4
1 1 1 -1
2 1 2
2 2 4
2 3 3
2 3 4
Output
2
2
1
1
Note

$$$^1$$$ An array $$$c$$$ is called a subsequence of an array $$$b$$$ if it is possible to remove a certain number of elements from the array $$$b$$$ (possibly zero) so that the array $$$c$$$ is formed. The empty array is a subsequence of any array.