Назвемо масив цілих чисел $d_1, d_2, \ldots, d_m$ хорошим, якщо його довжина рівна $0$, або для будь-якого $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$ довжини $n$, що складається з чисел $-1$ та $1$.
Необхідно виконати $q$ запитів. Запити бувають двох типів:
- замінити елемент $a_p$ на $-a_p$, де $p$~--- параметр запиту;
- знайти красу масиву, що складається з елементів $[a_{l},a_{l+1},\ldots,a_r]$, де $(l, r)$~--- параметри запиту.
Вхідні дані
У першому рядку задано два цілі числа $n$, $q$ $(1\le n, q\le 5 \cdot 10^5)$~--- довжина масиву $a$ та кількість запитів відповідно.
У другому рядку задано $n$ цілих чисел $a_1, a_2, \ldots, a_n$ $(a_i \in \{-1, 1\})$~--- елементи масиву $a$.
У наступних $q$ рядках задано опис запитів. Перше з чисел $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$ Масив $c$ називається підпослідовністю масиву $b$, якщо можливо видалити певну кількість елементів з масиву $b$ (можливо, нульову) так, щоб утворився масив $c$. Порожній масив є підпослідовністю будь-якого масиву.
Приклади
Вхідні дані
5 4 1 1 1 -1 1 2 1 5 1 3 2 1 4 2 2 5
Відповідь
5 2 3
Вхідні дані
4 4 1 1 1 -1 2 1 2 2 2 4 2 3 3 2 3 4
Відповідь
2 2 1 1
Оцінювання
- ($2$ бали): $a_i = (-1)^{i+1}$ для $1 \le i \le n$, а також немає запитів першого типу;
- ($7$ балів): $n \le 16$, а також немає запитів першого типу;
- ($21$ бал): $n, q \le 100$;
- ($20$ балів): $n, q \le 3000$;
- ($27$ балів): $n, q \leq 2 \cdot 10^5$, а також немає запитів першого типу;
- ($14$ балів): $n, q \leq 2 \cdot 10^5$;
- ($9$ балів): без додаткових обмежень.