ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2064. Гусеницы

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Юный садовод давно не приезжал в сад, и поэтому дела там плохи: в саду появилось n гусениц.
Приехал Кирилл в сад и решил повеселиться с гусеницами: устроить соревнование — «гусеничный заполз».
По команде Кирилла все гусеницы стартуют из своих домиков на земле и ползут по дереву. Но гусеницы довольно быстро устают. Каждая гусеница после того, как проползёт ti см, отдыхает ti минут, в это время гусеница сползает вниз по дереву. Скорость любой гусеницы — 1 см/мин, скорость сползания — тоже 1 см/мин.
Кириллу интересно, на какой высоте находится гусеница-лидер в фиксированные моменты времени.

Исходные данные

В первой строке записано одно целое число n — количество гусениц (1 ≤ n ≤ 106).
Во второй строке записаны n целых чисел ti, характеризующих гусениц (1 ≤ ti ≤ 109).
В третьей строке записано одно число q — количество моментов времени, интересующих Кирилла (1 ≤ q ≤ 106).
Затем, по одному в строке, описаны запросы Кирилла. Каждый запрос описывается одним числом xi — количество минут, прошедших с начала соревнования (1 ≤ xi ≤ 106).

Результат

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

Пример

исходные данныерезультат
4
1 3 2 1
12
1
2
3
4
5
6
7
8
9
10
11
12
1
2
3
2
1
2
1
2
3
2
1
0
Автор задачи: Никита Сивухин (подготовка — Алексей Данилюк, Никита Сивухин)
Источник задачи: Уральская региональная командная олимпиада по программированию 2015