База даних з високим навантаженням#9525

База даних з високим навантаженням

1 секунда

128 мегабайтів

Легка

Генрі описує сценарій міграції бази даних з високим навантаженням. Скрипт являє собою список з $n$ транзакцій. $i$ -та транзакція складається з $a_{i}$ a_i запитів. Генрі хоче розділити скрипт на мінімально можливу кількість пакетів, де кожен пакет містить або одну транзакцію, або послідовність послідовних транзакцій, а загальна кількість запитів у кожному пакеті не перевищує $t$ .

На жаль, Генрі не знає точного значення $t$ для продуктивної бази даних, тому він збирається оцінити мінімальну кількість пакетів для $q$ можливих значень $t$ : $t_{1}, t_{2}, \dots, t_{q}$ t_1, t_2, \ldots, t_q. Допоможіть Генрі обчислити кількість транзакцій для кожного з них.

Вхідні дані

Перший рядок містить кількість транзакцій $n$ ( $1 \leq n \leq 200000$ 1 \le n \le 200\,000) у міграційному скрипті.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n — кількість запитів у кожній транзакції ( $1 \leq a_{i}$ 1 \le a_i; $\sum a_{i} \leq 1 0^{6}$ \sum a_i \le 10^6).

Третій рядок містить кількість запитів $q$ ( $1 \leq q \leq 1 0^{5}$ 1 \le q \le 10^5).

Четвертий рядок містить $q$ цілих чисел $t_{1}, t_{2}, \dots, t_{q}$ t_1, t_2, \ldots, t_q ( $1 \leq t_{i} \leq \sum a_{i}$ 1 \le t_i \le \sum a_i).

Вихідні дані

Виведіть $q$ рядків. У $i$ -му рядку виведіть мінімальну кількість пакетів, кожен з яких містить не більше $t_{i}$ t_i запитів. Якщо неможливо розбити скрипт на пакети для деякого $t_{i}$ t_i, виведіть "Impossible".

Пам'ятайте, що ви не можете змінювати порядок транзакцій, вам дозволено лише групувати послідовні транзакції в пакет.

Приклади

Приклад 1