Назвемо масив цілих чисел $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$ запитів. Запити бувають двох типів:

1. замінити елемент $a_p$ на $-a_p$, де $p$~--- параметр запиту;
2. знайти красу масиву, що складається з елементів $[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

Оцінювання

1. ($2$ бали): $a_i = (-1)^{i+1}$ для $1 \le i \le n$, а також немає запитів першого типу;
2. ($7$ балів): $n \le 16$, а також немає запитів першого типу;
3. ($21$ бал): $n, q \le 100$;
4. ($20$ балів): $n, q \le 3000$;
5. ($27$ балів): $n, q \leq 2 \cdot 10^5$, а також немає запитів першого типу;
6. ($14$ балів): $n, q \leq 2 \cdot 10^5$;
7. ($9$ балів): без додаткових обмежень.