Проста підпослідовність#11813
Назвемо масив цілих чисел d_1, d_2, \ldots, d_m хорошим, якщо його довжина рівна , або для будь-якого 1\le i\le m обидва значення \sum\limits_{j=1}^{i} d_j та \sum\limits_{j=i}^{m} d_j є невід'ємними. Тут \sum\limits_{j=l}^{r} d_j позначає d_l+d_{l+1}+\ldots+d_{r}.
Визначимо красу масиву як довжину найдовшої його хорошої підпослідовності^1.
Задано масив довжини , що складається з чисел та .
Необхідно виконати запитів. Запити бувають двох типів:
замінити елемент a_p на -a_p, де — параметр запиту;
знайти красу масиву, що складається з елементів [a_{l},a_{l+1},\ldots,a_r], де (l, r) — параметри запиту.
У першому рядку задано два цілі числа , (1\le n, q\le 5 \cdot 10^5) — довжина масиву та кількість запитів відповідно.
У другому рядку задано цілих чисел a_1, a_2, \ldots, a_n (a_i \in \{-1, 1\}) — елементи масиву .
У наступних рядках задано опис запитів. Перше з чисел type_i (1 \le type_i \le 2) позначає тип запиту. Запити першого типу задані у форматі «1 p» (1 \le p \le n), а запити другого типу задані у форматі «2 l r» (1 \le l \le r \le n).
Для кожного запиту другого типу в окремому рядку виведіть одне ціле число — красу відповідного масиву.
Приклад 1
Приклад 2
^1 Масив називається підпослідовністю масиву , якщо можливо видалити певну кількість елементів з масиву (можливо, нульову) так, щоб утворився масив . Порожній масив є підпослідовністю будь-якого масиву.
( бали): a_i = (-1)^{i+1} для 1 \le i \le n, а також немає запитів першого типу;
( балів): n \le 16, а також немає запитів першого типу;
( бал): n, q \le 100;
( балів): n, q \le 3000;
( балів): n, q \leq 2 \cdot 10^5, а також немає запитів першого типу;
( балів): n, q \leq 2 \cdot 10^5;
( балів): без додаткових обмежень.