Для любой последовательности говорят, что её можно «удалить до пустоты», если её можно сделать пустой за конечное число операций удаления. Операция удаления определяется следующим образом:
- Пусть текущая длина последовательности равна $k$. Тогда удаляются все элементы последовательности, равные $k$.
Дана последовательность $a$ длины $n$ и $m$ операций модификации. После каждой $i$-й операции необходимо ответить на вопрос: сколько ещё элементов нужно изменить в текущей последовательности $a$, чтобы её можно было удалить до пустоты?
Каждая операция модификации представляет собой либо изменение одного элемента, либо прибавление числа к каждому элементу последовательности, либо вычитание числа из каждого элемента последовательности.
Входные данные
Первая строка содержит два целых положительных числа $n$ и $m$, обозначающих длину последовательности и количество операций модификации соответственно.
Вторая строка содержит $n$ целых положительных чисел, представляющих последовательность $a$, где $i$-е число — это $a_i$.
Далее следуют $m$ строк, каждая из которых содержит два целых числа $p$ и $x$, описывающих операцию модификации.
Если $1 \le p \le n$, это операция точечного изменения: $a_p$ заменяется на $x$.
Если $p = 0$, это операция изменения всей последовательности: к каждому элементу прибавляется $x$.
Выходные данные
Выведите $m$ строк, по одному целому числу в каждой. $i$-я строка должна содержать ответ после выполнения первых $i$ операций.
Примеры
Пример 1
3 9 1 2 3 1 1 0 1 0 1 0 1 2 2 3 2 0 -1 0 -1 0 -1
Выходные данные 1
0 1 2 3 2 1 1 2 2
Примечание
После первой модификации последовательность равна $(1, 2, 3)$, её можно удалить до пустоты без изменений.
После четвёртой модификации последовательность равна $(4, 5, 6)$, необходимо изменить все три числа, чтобы её можно было удалить до пустоты.
После шестой модификации последовательность равна $(4, 2, 2)$, достаточно изменить первый элемент на $3$, чтобы последовательность можно было удалить до пустоты.
После девятой модификации последовательность равна $(1, -1, -1)$, можно изменить второй элемент на $2$ и третий на $3$, чтобы удалить последовательность до пустоты.
Подзадачи
| Подзадача # | Баллы | $n \le$ | $m \le$ | Выполняется ли $p>0$ |
|---|---|---|---|---|
| $1$ | $7$ | $5$ | $10$ | Нет |
| $2$ | $14$ | $300$ | $1$ | Да |
| $3$ | $15$ | $3000$ | $1$ | Да |
| $4$ | $11$ | $3000$ | $3000$ | Да |
| $5$ | $13$ | $10^5$ | $10^5$ | Да |
| $6$ | $32$ | $10^5$ | $10^5$ | Нет |
| $7$ | $8$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | Нет |
Для $100\%$ данных:
- $1 \le n, m \le 1.5 \times 10^5$
- $1 \le a_i \le n$
- $0 \le p \le n$
- Если $p > 0$, то $1 \le x \le n$.
- Если $p = 0$, то $x = -1$ или $1$.