Частное пространство
Люди посещают кинотеатр группами (или в одиночку), но обычно предпочитают общаться только внутри своей группы. Будучи скандинавами, каждая группа хотела бы сидеть на расстоянии как минимум одного места от другой группы для обеспечения приватности, если только они не находятся в конце ряда. Количество мест в ряду начинается с X и уменьшается на одно место в каждом следующем ряду (до одного места в ряду). Количество групп разного размера задано вектором (N_1, ..., N_n), где N_1 — это количество одиночных посетителей, N_2 — количество пар и так далее.
Ваша задача — определить ширину ряда X, самого широкого ряда, который позволит разместить всех посетителей, используя минимальное количество рядов. Учтите, что вместимость кинотеатра ограничена, и самый широкий ряд не может превышать 12 мест.
Входные данные
Первая строка входных данных содержит одно целое число n (1 ≤ n ≤ 12), которое обозначает размер самой большой группы в тестовом случае. Следующая строка содержит n целых чисел, где i-е число (индексация с 1) указывает количество групп из i человек, которым необходимо найти места.
Выходные данные
Выведите одно число — размер самого узкого самого широкого ряда, который сможет разместить всех гостей. Если это число больше 12, выведите impossible.