База данных с высокой нагрузкой
База данных с высокой нагрузкой
Генри описывает сценарий миграции базы данных с высокой нагрузкой. Скрипт представляет собой список из n транзакций. i -я транзакция состоит из ai
запросов. Генри хочет разделить скрипт на минимально возможное количество пакетов, где каждый пакет содержит либо одну транзакцию, либо последовательность последовательных транзакций, а общее количество запросов в каждом пакете не превышает t.
К сожалению, Генри не знает точного значения t для производственной базы данных, поэтому он собирается оценить минимальное количество пакетов для q возможных значений t: t1
, t2
, . . . , tq
. Помогите Генри рассчитать количество транзакций для каждой из них.
Входные данные
Первая строка содержит количество транзакций n (1 ≤ n ≤ 200 000) в миграционном скрипте.
Вторая строка содержит n целых чисел a1
, a2
, . . . , an
- количество запросов в каждой транзакции (1 ≤ ai
; Σ ai
≤ 106
).
Третья строка содержит количество запросов q (1 ≤ q ≤ 105
).
Четвертая строка содержит q целых чисел t1
, t2
, . . . , tq
(1 ≤ ti
≤ Σ ai
).
Выходные данные
Выведите q строк. В i-ой строке выведите минимальное количество пакетов, каждый из которых содержит не более ti
запросов. Если невозможно разбить скрипт на пакеты для некоторого ti
, то выведите "Impossible".
Помните, что Вы не можете переупорядочивать транзакции, Вам разрешено только группировать последовательные транзакции в пакет.
6 4 2 3 1 3 4 8 10 2 5 4 6 7 8 8
2 Impossible 4 5 4 3 3 3