E. Марк и профессор Коро
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После просмотра одного аниме перед сном Марку снится, что он стоит в старом классе с меловой доской, на которой записана последовательность из $$$n$$$ положительных целых чисел $$$a_1, a_2,\dots,a_n$$$.

Затем в класс заходит профессор Коро. Он может выполнять следующую операцию:

  • выбрать целое число $$$x$$$ которое присутствует на доске хотя бы $$$2$$$ раза,
  • стереть эти $$$2$$$ вхождения,
  • записать число $$$x+1$$$ на доску.

После чего профессор Коро задает марку вопрос: «Какое максимально возможное число может появиться на доске после некоторого количества таких операций?»

Марк быстро отвечает на этот вопрос, но он всё ещё медленнее профессора Коро. Поэтому профессор Коро решает задать Марку дополнительные вопросы. Он будет менять изначальную последовательность чисел на доске $$$q$$$ раз. Каждый раз он будет выбирать положительные целые числа $$$k$$$ и $$$l$$$, затем менять $$$a_k$$$ на $$$l$$$. После каждого такого изменения он будет спрашивать у Марка ответ на тот же самый вопрос.

Помогите Марку ответить на вопросы быстрее профессора Коро!

Обратите внимание, что изменения начальной последовательности на доске сохраняются. Изменения, внесенные в последовательность $$$a$$$, будут так же применяться при обработке следующих изменений.

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1\leq a_i\leq 2\cdot 10^5$$$).

Затем следуют $$$q$$$ строк, каждая из которых содержит два целых числа $$$k$$$ и $$$l$$$ ($$$1\leq k\leq n$$$, $$$1\leq l\leq 2\cdot 10^5$$$), означающие изменение $$$a_k$$$ на значение $$$l$$$.

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

Выведите $$$q$$$ строк, $$$i$$$-я строка должна содержать единственное целое число — ответ после $$$i$$$-го изменения.

Примеры
Входные данные
5 4
2 2 2 4 5
2 3
5 3
4 1
1 4
Выходные данные
6
5
4
5
Входные данные
2 1
200000 1
2 200000
Выходные данные
200001
Примечание

В первом примере программа должна обработать $$$4$$$ изменения.

После первого обновления последовательность на доске выглядит как $$$[2,3,2,4,5]$$$. Одна из возможных последовательностей операций, достигающих числа $$$6$$$, такая:

  • Изначально, на доске числа $$$[2,3,2,4,5]$$$.
  • Удаляем два вхождения числа $$$2$$$ и записываем $$$3$$$, получая $$$[3,4,5,\color{red}{3}]$$$.
  • Удаляем два вхождения числа $$$3$$$ и записываем $$$4$$$, получая $$$[4,5,\color{red}{4}]$$$.
  • Удаляем два вхождения числа $$$4$$$ и записываем $$$5$$$, получая $$$[5,\color{red}{5}]$$$.
  • Удаляем два вхождения числа $$$5$$$ и записываем $$$6$$$, получая $$$[\color{red}{6}]$$$.

Затем, во время второго изменения, массив станет равным $$$[2,3,2,4,3]$$$. В этот раз Марк не может достичь числа $$$6$$$. Однако одна из последовательностей операций, приводящая к числу $$$5$$$, такая:

  • Изначально, на доске числа $$$[2,3,2,4,3]$$$.
  • Удаляем два вхождения числа $$$2$$$ и записываем $$$3$$$, получая $$$[3,4,3,\color{red}{3}]$$$.
  • Удаляем два вхождения числа $$$3$$$ и записываем $$$4$$$, получая $$$[3,4,\color{red}{4}]$$$.
  • Удаляем два вхождения числа $$$4$$$ и записываем $$$5$$$, получая $$$[3,\color{red}{5}]$$$.

Во время третьего изменения массив станет равным $$$[2,3,2,1,3]$$$. Один из возможных вариантов достичь числа $$$4$$$ такой:

  • Изначально, на доске числа $$$[2,3,2,1,3]$$$.
  • Удаляем два вхождения числа $$$3$$$ и записываем $$$4$$$, получая $$$[2,2,1,\color{red}{4}]$$$.