eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Чорна скринька

Чорна скринька

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Чорна Скринька являє собою примітивну базу даних. Вона може зберігати масив цілих чисел, а також має спеціальну змінну 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, m30000. Для вище наведеного прикладу 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) відсортовані у неспадаючому порядку, nm, а для кожного p (1pn) має місце нерівність pu(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). Всі числа відокремлені проміжками і (або) символом переводу на новий ряодок.

Вихідні дані

Вивести відповіді Чорної Скриньки на послідовність виконаних транзакцій. Кожне число потрібно виводитити в окремому рядку.

Приклад

Вхідні дані #1
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
Вихідні дані #1
3
3
1
2