Simple Subsequence#11813
We call an array of integers d_1, d_2, \ldots, d_m good if its length is equal to , 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 of length , which consists of numbers and .
You need to perform queries. The queries are of two types:
replace the element a_p with -a_p, where — the parameter of the query;
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.
In the first line, two integers , are given (1\le n, q\le 5 \cdot 10^5) — the length of the array and the number of queries, respectively.
In the second line, integers a_1, a_2, \ldots, a_n (a_i \in \{-1, 1\}) are given — the elements of the array .
In the next 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).
For each query of the second type, output one integer in a separate line — the beauty of the corresponding array.
Example 1
Example 2
^1 An array is called a subsequence of an array if it is possible to remove a certain number of elements from the array (possibly zero) so that the array is formed. The empty array is a subsequence of any array.
( points): a_i = (-1)^{i+1} for 1 \le i \le n, and there are no type one queries;
( points): n \le 16, and there are no type one queries;
( points): n, q \le 100;
( points): n, q \le 3000;
( points): n, q \leq 2 \cdot 10^5, and there are no type one queries;
( points): n, q \leq 2 \cdot 10^5;
( points): no additional restrictions.