eolymp
bolt
Try our new interface for solving problems
Məsələlər

Черный Ящик

Черный Ящик

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 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)).

Giriş verilənləri

Состоит из следующего набора чисел: m, n, A(1), A(2), ..., A(m), u(1), u(2), ..., u(n). Все числа разделены пробелами и (или) символом перевода на новую строку.

Çıxış verilənləri

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

Nümunə

Giriş verilənləri #1
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
Çıxış verilənləri #1
3
3
1
2