D. Мультимножество
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
28 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на нестандартное ограничение памяти.

Вам задано мультимножество из $$$n$$$ целых чисел. Вы должны обрабатывать запросы двух типов:

  • добавить элемент $$$k$$$ в мультимножество;
  • найти $$$k$$$-ю порядковую статистику в мультимножестве и удалить ее.

Напомним, что $$$k$$$-я порядковая статистика в мультимножестве — это элемент, который будет на позиции $$$k$$$, если выписать все его элементы в порядке неубывания. Например, если в мультимножестве содержатся числа $$$1$$$, $$$4$$$, $$$2$$$, $$$1$$$, $$$4$$$, $$$5$$$, $$$7$$$ и $$$k = 3$$$, то необходимо найти $$$3$$$-й элемент в списке $$$[1, 1, 2, 4, 4, 5, 7]$$$, и он равен $$$2$$$. Если в мультимножестве несколько копий удаляемого элемента, удаляется только одна из них.

После всех запросов выведите любое число, принадлежащее мультимножеству, или сообщите, что оно пустое.

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

В первой строке заданы два числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — количество элементов в мультимножестве и количество запросов, соответственно.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le n$$$) — элементы мультимножества.

В третьей строке заданы $$$q$$$ целых чисел $$$k_1$$$, $$$k_2$$$, ..., $$$k_q$$$, каждое из которых описывает очередной запрос следующим образом:

  • если $$$1 \le k_i \le n$$$, то $$$i$$$-й запрос — «добавить $$$k_i$$$ в мультимножество»;
  • если $$$k_i < 0$$$, то $$$i$$$-й запрос — «удалить $$$|k_i|$$$-ю порядковую статистику». Гарантируется, что в таком случае $$$|k_i|$$$ не превосходит размера множества.
Выходные данные

Если после всех запросов мультимножество оказалось пустым, выведите $$$0$$$.

Иначе выведите любое число, принадлежащее мультимножеству.

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

В первом примере последовательно удаляются все элементы мультимножества.

Во втором примере последовательно удалятся элементы $$$5$$$, $$$1$$$, $$$4$$$, $$$2$$$.

В третьем примере $$$6$$$ — не единственный ответ.