Юный садовод давно не приезжал в сад, и поэтому дела там плохи: в саду появилось n гусениц.

Приехал Кирилл в сад и решил повеселиться с гусеницами: устроить соревнование — «гусеничный заполз».

По команде Кирилла все гусеницы стартуют из своих домиков на земле и ползут по дереву. Но гусеницы довольно быстро устают. Каждая гусеница после того, как проползёт t_i см, отдыхает t_i минут, в это время гусеница сползает вниз по дереву. Скорость любой гусеницы — 1 см/мин, скорость сползания — тоже 1 см/мин.

Кириллу интересно, на какой высоте находится гусеница-лидер в фиксированные моменты времени.

В первой строке записано одно целое число n — количество гусениц (1 ≤ n ≤ 10⁶).

Во второй строке записаны n целых чисел t_i, характеризующих гусениц (1 ≤ t_i ≤ 10⁹).

В третьей строке записано одно число q — количество моментов времени, интересующих Кирилла (1 ≤ q ≤ 10⁶).

Затем, по одному в строке, описаны запросы Кирилла. Каждый запрос описывается одним числом x_i — количество минут, прошедших с начала соревнования (1 ≤ x_i ≤ 10⁶).

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