Пусть у нас имеется массив из \(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\) запросов следующего вида — изменить значение в позиции. После каждого изменения вам необходимо вывести вес полученного массива. Обратите внимание, что изменения не независимы (изменение сохраняется на будущее).
Выходные данные
После каждого запроса выведите вес полученного массива.
Примечание
После первого запроса изменения массив имеет вид \([25, 40, 30, 20, 10]\). Вес равен \(3\).
После второго запроса изменения массив имеет вид \([25, 40, 45, 20, 10]\). Вес все еще равен \(3\).
После третьего запроса изменения массив имеет вид \([48, 40, 45, 20, 10]\). Вес равен \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
50 40 30 20 10
1 25
3 45
1 48
|
3
3
4
|