D. Мусорная задача
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вова решил прибраться в своей комнате. Комната может быть представлена как координатная ось $$$OX$$$. Всего в комнате есть $$$n$$$ кучек мусора, координата $$$i$$$-й кучки равна целому числу $$$p_i$$$. Все кучки имеют различные координаты.

Давайте определим генеральную уборку как следующий процесс. Цель этого процесса —- собрать все кучки в не более чем двух различных $$$x$$$ координатах. Чтобы достичь этой цели, Вова может совершить некоторое (возможно, нулевое) количество ходов. За один ход он может выбрать какой-либо $$$x$$$ и переместить все кучки из $$$x$$$ в $$$x+1$$$ или $$$x-1$$$ при помощи метлы. Заметьте, что он не может выбирать, сколько кучек он будет двигать.

Также существует два типа запросов:

  • $$$0$$$ $$$x$$$ — удалить кучку мусора из координаты $$$x$$$. Гарантируется, что в координате $$$x$$$ находится кучка в этот момент времени.
  • $$$1$$$ $$$x$$$ — добавить кучку мусора в координату $$$x$$$. Гарантируется, что в координате $$$x$$$ не находится кучки мусора в этот момент времени.

Заметьте, что в какой-либо момент времени в комнате может быть нулевое количество кучек мусора.

Вова хочет знать минимальное количество ходов, которое ему необходимо затратить, если он решит сделать генеральную уборку перед всеми запросами. Он также хочет знать это количество ходов после применения каждого запроса. Запросы применяются в заданном порядке. Заметьте, что генеральная уборка на самом деле не происходит и не изменяет состояние кучек. Она используется только для того, чтобы посчитать количество ходов.

Для лучшего понимания, пожалуйста, прочтите секцию Примечание ниже, чтобы увидеть объяснение первого примера.

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

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

Вторая строка входных данных содержит $$$n$$$ различных целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^9$$$), где $$$p_i$$$ равно координате $$$i$$$-й кучки.

Следующие $$$q$$$ строк описывают запросы. $$$i$$$-й запрос описывается двумя целыми числами $$$t_i$$$ и $$$x_i$$$ ($$$0 \le t_i \le 1; 1 \le x_i \le 10^9$$$), где $$$t_i$$$ равно $$$0$$$, если вам необходимо удалить кучку из координаты $$$x_i$$$, и равно $$$1$$$, если вам необходимо добавить кучку в координату$$$x_i$$$. Гарантируется, что для $$$t_i = 0$$$ такая кучка находится в текущем множестве кучек, а для $$$t_i = 1$$$ такая кучка не находится в текущем множестве кучек.

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

Выведите $$$q+1$$$ целое число: минимальное количество ходов, которое нужно Вове, чтобы устроить генеральную уборку перед первым запросом и после каждого из $$$q$$$ запросов.

Примеры
Входные данные
5 6
1 2 6 8 10
1 4
1 9
0 6
0 10
1 100
1 50
Выходные данные
5
7
7
5
4
8
49
Входные данные
5 8
5 1 2 4 3
0 1
0 2
0 3
0 4
0 5
1 1000000000
1 1
1 500000000
Выходные данные
3
2
1
0
0
0
0
0
499999999
Примечание

Рассмотрим первый пример.

Изначально множество кучек равно $$$[1, 2, 6, 8, 10]$$$. Ответ перед первым запросом равен $$$5$$$, потому что вы можете сдвинуть все кучки из $$$1$$$ в $$$2$$$ за один ход, все кучки из $$$10$$$ в $$$8$$$ за $$$2$$$ хода и все кучки из $$$6$$$ в $$$8$$$ за $$$2$$$ хода.

После первого запроса множество превращается в $$$[1, 2, 4, 6, 8, 10]$$$. Тогда ответ равен $$$7$$$, потому что вы можете сдвинуть все кучки из $$$6$$$ в $$$4$$$ за $$$2$$$ хода, все кучки из $$$4$$$ в $$$2$$$ за $$$2$$$ хода, все кучки из $$$2$$$ в $$$1$$$ за $$$1$$$ ход и все кучки из $$$10$$$ в $$$8$$$ за $$$2$$$ хода.

После второго запроса множество превращается в $$$[1, 2, 4, 6, 8, 9, 10]$$$, а ответ остается таким же самым (и предыдущая последовательность ходов может быть применена к текущему множеству кучек).

После третьего запроса множество превращается в $$$[1, 2, 4, 8, 9, 10]$$$, а ответ равен $$$5$$$, потому что вы можете сдвинуть все кучки из $$$1$$$ в $$$2$$$ за $$$1$$$ ход, все кучки из $$$2$$$ в $$$4$$$ за $$$2$$$ хода, все кучки из $$$10$$$ в $$$9$$$ за $$$1$$$ ход и все кучки из $$$9$$$ в $$$8$$$ за $$$1$$$ ход.

После четвертого запроса множество превращается в $$$[1, 2, 4, 8, 9]$$$, а ответ остается почти таким же самым (предыдущая последовательность может быть применена полностью, исключая перемещение кучек из $$$10$$$).

После пятого запроса множество превращается в $$$[1, 2, 4, 8, 9, 100]$$$. Вы можете сдвинуть все кучки из $$$1$$$ и дальше в $$$9$$$, а $$$100$$$ оставить на ее месте. Таким образом, ответ равен $$$8$$$.

После шестого запроса множество превращается в $$$[1, 2, 4, 8, 9, 50, 100]$$$. Ответ равен $$$49$$$ и может быть получен при помощи почти такой же последовательности ходов, как и после предыдущего запроса. Единственная разница заключается в том, что вы также должны двигать все кучки из $$$50$$$ в $$$9$$$.