Полка с книгами
(Время: 2 сек. Память: 32 Мб Сложность: 30%)
Мальчик Вася очень любит читать, и у него дома много книг, которые он хранит на большой книжной полке. Вася любит порядок, поэтому он решил расположить свои книги по возрастанию количества страниц в них слева направо. В процессе такой сортировки он заметил, что все книги имеют разное число страниц, по которому любая Васина книга определяется однозначно.
Однажды летом Вася уехал в деревню к бабушке, а его родители заинтересовались увлечением сына и решили познакомиться с его коллекцией. Сначала папа взял несколько подряд стоящих книг слева, а затем мама забрала все оставшиеся книги, которые изначально стояли справа.
Перед возвращением Васи домой родители вернули книги назад на полку: папа поставил все книги, которые брал, слева, а мама аналогичным образом поставила остальные книги справа. Однако родители не заметили того, что книги были упорядочены, и поставили их произвольным образом.
Вернувшись домой, Вася заметил, что порядок книг нарушен. Допросив маму, он узнал то, каким образом случилось такое перемешивание, и его заинтересовал вопрос: сколько книг мог брать папа, и сколько книг могла брать мама?
По итоговому расположению книг помогите Васе ответить на его вопрос. При этом достаточно сказать, сколько книг мог взять папа (этого достаточно, т.к. мама взяла все остальные – и это число легко вычислить). При этом известно, что каждый из родителей взял хотя бы одну книгу.
Входные данные
Первая строка входного файла INPUT.TXT содержит единственное число N – количество книг на полке у Васи. Во второй строке записаны N целых чисел Ai – информация о количестве страниц в каждой книге слева направо на тот момент, когда Вася вернулся домой. Гарантируется, что все значения Ai различны.
Ограничения: 2 ≤ N ≤ 3×105, 1 ≤ Ai ≤ 109.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите целое число K – количество возможных вариантов набора книг, которые мог взять папа. Во второй строке выведите в возрастающем порядке количество книг в каждом из этих наборов.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 1 2 3 | 2 1 2 |
2 | 5 2 1 5 9 6 | 2 2 3 |
Система оценки
Решения, работающие только при N ≤ 1000, будут оцениваться в 40 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|