E. Фокус с подмножествами
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваня придумал интересный фокус с множеством целых чисел.

Пусть у фокусника есть множество положительных целых чисел $$$S$$$. Он называет некоторое положительное целое число $$$x$$$. Зритель должен выбрать, не показывая фокуснику, некоторое подмножество $$$S$$$ (возможно пустое). После этого зритель называет фокуснику размер выбранного подмножества. Фокус заключается в том, что после этого фокусник отгадывает: верно ли, что сумма элементов выбранного подмножества не превосходит $$$x$$$. Для пустого подмножества сумма предполагается равной $$$0$$$.

Ване очень понравился этот фокус, поэтому он начал готовиться к тому, чтобы показать его публике. Для этого он приготовил некоторое множество различных положительных целых чисел $$$S$$$. Конечно, Ваня хочет, чтобы фокус обязательно получился. Он называет положительное целое число $$$x$$$ неудачным, если не может быть точно уверен, что фокус пройдет удачно для любого подмножества, которое выберет зритель.

Чтобы оценить, насколько хорошее множество $$$S$$$ он выбрал, он хочет посчитать количество неудачных положительных целых чисел для него.

Также Ваня планирует протестировать различные множества $$$S$$$. Поэтому он просит вас написать программу, которая найдет количество неудачных положительных целых чисел для изначального множества $$$S$$$ и для множества $$$S$$$ после каждого изменения. Ваня сделает $$$q$$$ изменений своего множества, каждое изменение будет одного из двух видов:

  • Добавить новое число $$$a$$$ в множество $$$S$$$.
  • Удалить некоторое число $$$a$$$ из множества $$$S$$$.
Входные данные

В первой строке находятся два целых числа $$$n$$$, $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$) — размер изначального множества $$$S$$$ и количество изменений.

В следующей строке находятся $$$n$$$ различных целых чисел $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \leq s_i \leq 10^{13}$$$) — элементы изначального множества $$$S$$$.

В каждой из следующих $$$q$$$ строк находятся два целых числа $$$t_i$$$, $$$a_i$$$ ($$$1 \leq t_i \leq 2$$$, $$$1 \leq a_i \leq 10^{13}$$$), описывающих очередное изменение.

  • Если $$$t_i = 1$$$, то это операция добавления нового числа $$$a_i$$$ в множество $$$S$$$. Гарантируется, что этого числа не было в множестве $$$S$$$ до выполнения операции.
  • Если $$$t_i = 2$$$, то это операция удаления числа $$$a_i$$$ из множества $$$S$$$. Гарантируется, что это число было в множестве $$$S$$$ до выполнения операции.
Выходные данные

Выведите $$$q + 1$$$ строку.

В первой строке выведите количество неудачных положительных целых чисел для изначального множества $$$S$$$. В следующих $$$q$$$ строках выведите количество неудачных положительных чисел для множества $$$S$$$ после каждого изменения.

Пример
Входные данные
3 11
1 2 3
2 1
1 5
1 6
1 7
2 6
2 2
2 3
1 10
2 5
2 7
2 10
Выходные данные
4
1
6
12
19
13
8
2
10
3
0
0
Примечание

В первом тесте изначальное $$$S = \{1, 2, 3\}$$$. Для этого множества фокус может не получиться при $$$x \in \{1, 2, 3, 4\}$$$. Например, если $$$x = 4$$$, то зритель может загадать подмножество $$$\{1, 2\}$$$, сумма элементов которого равна $$$3 \leq x$$$, а может загадать подмножество $$$\{2, 3\}$$$, сумма элементов которого равна $$$5 > x$$$. Однако в обоих случаях зритель назовет фокуснику размер подмножества $$$2$$$, поэтому он не сможет точно сделать правильный ответ. При этом поскольку подмножество размера $$$3$$$ единственно, а сумма в любом подмножестве меньшего размера не превосходит $$$5$$$, все $$$x \ge 5$$$ не являются неудачными.