B. Парковка

В центре города П. построили большой и красивый торговый центр. Его парковка состоит из N уровней. На i-м уровне есть a_i парковочных мест. При въезде на парковку водителю выдаётся талон, в котором указан минимальный номер уровня, на котором есть свободные места. Получив подобный талон, водитель отправляется на указанный уровень и занимает там место. По окончании визита в торговый центр, покупатель уезжает, освобождая парковочное место.

Естественно, в течение дня на парковку приезжает и уезжает большое количество автомобилей, поэтому для выдачи талонов на парковку хозяева центра хотят использовать программу. От вас требуется такую программу реализовать.

Формат входного файла

В первой строке входного файла находится единственное число N – количество уровней на парковке (1 ≤ N ≤ 10⁵). Во второй строке находится N чисел a_i – количество парковочных мест на каждом уровне (1 ≤ a_i ≤ 1000).

В третьей строке входного файла находится число M – количество событий, произошедших на парковке за день (1 ≤ M ≤ 10⁵). В четвёртой строке находится M чисел b_i, описывающих события. Если b_i = 0, значит на парковку приехал очередной автомобиль. Если же b_i = x > 0, значит, с уровня номер x уехал один из автомобилей, расположенных там. Конечно, во втором случае гарантируется, что x ≤ N и что в этот момент на уровне x находится хотя бы один автомобиль.

Известно, что мест для парковки автомобилей заведомо хватает, то есть при каждом появлении нового автомобиля для него есть хотя бы одно место.

Формат выходного файла

Выведите столько чисел, сколько раз событие <<приехал автомобиль>> встретилось во входном файле. Для каждого такого события выведите единственное число – номер на талоне, выдаваемом водителю этого автомобиля. Напоминаем, что этот номер должен быть равен минимальному номеру уровня, на котором есть свободные парковочные места.

Пример:

Решения, работающие при 1 ≤ N, M ≤ 1000 будут оцениваться из 60 баллов.

В первом примере первые два автомобиля помещаются на первый уровень парковки. Два следующих автомобиля нельзя поместить на первый уровень, поскольку все места там заняты. Таким образом, эти автомобили помещаются на второй уровень. Далее, один из автомобилей с первого уровня уезжает и следующий приехавший автомобиль может занять его место.

Источник: VII сетевая районная олимпиада Республики Карелия по информатике, XXIV Городская олимпиада школьников по информатике

Обсудить       Отправить решение



Версия для печати