Чорна скринька
Чорна Скринька являє собою примітивну базу даних. Вона може зберігати масив цілих чисел, а також має спеціальну змінну i. У початковий момент Чорна Скринька порожня, змінна i дорівнює 0. Чорна Скринька опрацьовує послідовність команд (транзакцій). Існує два типи транзакцій:
ADD(x): додати елемент x у Чорну Скриньку;
GET: збільшити i на 1 та вивести i-ий мінімальний елемент серед усіх чисел, що знаходяться у Чорній Скриньці.
Пам'ятайте, що i-ий мінімальний елемент знаходиться на i-ому місці після того як усі елементи Чорної Скрньки будуть відсортовані у неспадаючому порядку.
Розглянемо роботу чорної скриньки на прикладі:
Необхідно розробити ефективний алгоритм виконання заданої послідовності транзакцій. Максимальна кількість транзакцій ADD та GET дорівнює 30000 (кожного типу).
Опишемо послідовність транзакцій двома цілочисельними масивами:
1. A(1), A(2), ..., A(m): послідовність елементів, які будуть додаватись до Чорної Скриньки. Елементами є цілі числа, за модулем не більші 2 000 000 000, m ≤ 30000. Для вище наведеного прикладу A = (3, 1, -4, 2, 8, -1000, 2).
2. u(1), u(2), ..., u(n): послідовність вказує на кількість елементів у Чорній Скриньці у момент виконання першої, другої, ... n-ої транзакції GET. Для вище описаного прикладу u = (1, 2, 6, 6).
Робота Чорної Скриньки припускає, що числа у послідовності u(1), u(2), ..., u(n) відсортовані у неспадаючому порядку, n ≤ m, а для кожного p (1 ≤ p ≤ n) має місце нерівність p ≤ u(p) ≤ m. Це випливає з того, що для p-го елементу послідовності u ми виконуємо GET транзакцію, яка виводить p-ий мінімальний елемент з набору чисел A(1), A(2), ..., A(u(p)).
Вхідні дані
Складаються з наступного набору чисел: m, n, A(1), A(2), ..., A(m), u(1), u(2), ..., u(n). Всі числа відокремлені проміжками і (або) символом переводу на новий ряодок.
Вихідні дані
Вивести відповіді Чорної Скриньки на послідовність виконаних транзакцій. Кожне число потрібно виводитити в окремому рядку.