Олимпиадный тренинг

Задача . D. Мультимножество

Задача

Темы: Бинарный поиск Структуры данных *1900

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

Вам задано мультимножество из \(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\), \(1\), \(4\), \(2\).

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