H. Количество компонент
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть у нас имеется массив из $$$n$$$ различных чисел $$$a_1, a_2, \dots, a_n$$$. Построим граф на $$$n$$$ вершинах следующим образом: для любой пары вершин $$$i < j$$$ соединим вершины $$$i$$$ и $$$j$$$ ребром, если $$$a_i < a_j$$$. Назовем весом массива количество компонент в полученном графе. Например, вес массива $$$[1, 4, 2]$$$ равен $$$1$$$, вес массива $$$[5, 4, 3]$$$ равен $$$3$$$.

Вам необходимо выполнить $$$q$$$ запросов следующего вида — изменить значение в позиции. После каждого изменения вам необходимо вывести вес полученного массива. Обратите внимание, что изменения не независимы (изменение сохраняется на будущее).

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^5$$$) — размер массива и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — исходный массив.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$pos$$$ и $$$x$$$ ($$$1 \le pos \le n$$$, $$$1 \le x \le 10^6, x \ne a_{pos}$$$). Это значит, что необходимо сделать $$$a_{pos}=x$$$.

Гарантируется, что в любой момент времени все числа в массиве различны.

Выходные данные

После каждого запроса выведите вес полученного массива.

Пример
Входные данные
5 3
50 40 30 20 10
1 25
3 45
1 48
Выходные данные
3
3
4
Примечание

После первого запроса изменения массив имеет вид $$$[25, 40, 30, 20, 10]$$$. Вес равен $$$3$$$.

После второго запроса изменения массив имеет вид $$$[25, 40, 45, 20, 10]$$$. Вес все еще равен $$$3$$$.

После третьего запроса изменения массив имеет вид $$$[48, 40, 45, 20, 10]$$$. Вес равен $$$4$$$.