База данных с высокой нагрузкой
Генри описывает сценарий миграции базы данных с высокой нагрузкой. Скрипт представляет собой список из n транзакций. i -я транзакция состоит из a[i] запросов. Генри хочет разделить скрипт на минимально возможное количество пакетов, где каждый пакет содержит либо одну транзакцию, либо последовательность последовательных транзакций, а общее количество запросов в каждом пакете не превышает t.
К сожалению, Генри не знает точного значения t для производственной базы данных, поэтому он собирается оценить минимальное количество пакетов для q возможных значений t: t[1], t[2], . . . , t[q]. Помогите Генри рассчитать количество транзакций для каждой из них.
Входные данные
Первая строка содержит количество транзакций n (1 ≤ n ≤ 200 000) в миграционном скрипте.
Вторая строка содержит n целых чисел a[1], a[2], . . . , a[n] - количество запросов в каждой транзакции (1 ≤ a[i]; Σ a[i] ≤ 10^6).
Третья строка содержит количество запросов q (1 ≤ q ≤ 10^5).
Четвертая строка содержит q целых чисел t[1], t[2], . . . , t[q] (1 ≤ t[i] ≤ Σ a[i]).
Выходные данные
Выведите q строк. В i-ой строке выведите минимальное количество пакетов, каждый из которых содержит не более t[i] запросов. Если невозможно разбить скрипт на пакеты для некоторого t[i], то выведите "Impossible".
Помните, что Вы не можете переупорядочивать транзакции, Вам разрешено только группировать последовательные транзакции в пакет.