Дистанционный практикум по программированию

Иван работает менеджером автомобильной парковки. Из-за МФК (МФК — мировой финансовый кризис) его работа стала заметно скучнее: люди реже используют машины, в результате те всё больше времени стоят без дела на парковке. В результате Иван решил поразвлекаться. Парковка довольно новая, так что он может перемещать машины с места на место с помощью автоматики.

Однажды ему стало скучно (снова!) просто перемещать автомобили, и он придумал правило: теперь он никогда не ставит машину на то место, где раньше стояла машина того же производителя.

Все парковочные места пронумерованы целыми числами, начиная с 1. Оказалось, что автомобили произведены n компаниями, при этом всего a_i автомобилей i-й компании.

Иван уже поперемещал все машины, которые хотел, в результате чего все места с 1 по a₁ заняты продукцией 1-го производителя, с a₁ + 1 по a₁ + a₂ — 2-го, и так далее.

Через пять часов — открытие парковки, поэтому ему интересно начальное расположение автомобилей (владельцы не обрадуются, не найдя свою движимую собственность на месте...).

Ваша задача, во-первых, проверить, была ли совершена ошибка (то есть нарушил ли Иван правило перемещения). Если же этого не произошло, Иван планирует понадеяться на удачу и выбрать лексикографически минимальное расположение, которое могло быть изначально.

Одно расположение называется лексикографически меньше другого, если существует позиция i такая, что во всех позициях j < i они совпадают, а номер производителя автомобиля в i-й позиции в первом расположении меньше, чем во втором.

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

После того, как расположение выбрано, Иван решил посмотреть на некоторые части последовательности, которые он помнит лучше других. От вас требуется выяснить, как они выглядят.

Рассмотрим пример: на парковке 3 автомобиля первого производителя, 2 — второго и 2 — третьего. Тогда на первых трёх местах должны стоять автомобили производителей 2, 2, 3, соответственно (так как сейчас там стоят автомобили первого производителя). Следующее место будет занято автомобилем первого производителя. На пятое место следует поставить автомобиль третьего производителя, так как иначе на одной из двух последних позиций произойдёт нарушение правил. Наконец, на две последние позиции можно поставить два автомобиля первого производителя.