Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Полка с книгами

(Время: 2 сек. Память: 32 Мб Сложность: 30%)

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

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

Перед возвращением Васи домой родители вернули книги назад на полку: папа поставил все книги, которые брал, слева, а мама аналогичным образом поставила остальные книги справа. Однако родители не заметили того, что книги были упорядочены, и поставили их произвольным образом.

Вернувшись домой, Вася заметил, что порядок книг нарушен. Допросив маму, он узнал то, каким образом случилось такое перемешивание, и его заинтересовал вопрос: сколько книг мог брать папа, и сколько книг могла брать мама?

По итоговому расположению книг помогите Васе ответить на его вопрос. При этом достаточно сказать, сколько книг мог взять папа (этого достаточно, т.к. мама взяла все остальные – и это число легко вычислить). При этом известно, что каждый из родителей взял хотя бы одну книгу.

Входные данные

Первая строка входного файла INPUT.TXT содержит единственное число N – количество книг на полке у Васи. Во второй строке записаны N целых чисел Ai – информация о количестве страниц в каждой книге слева направо на тот момент, когда Вася вернулся домой. Гарантируется, что все значения Ai различны.

Ограничения: 2 ≤ N ≤ 3×105, 1 ≤ Ai ≤ 109.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите целое число K – количество возможных вариантов набора книг, которые мог взять папа. Во второй строке выведите в возрастающем порядке количество книг в каждом из этих наборов.

Примеры

INPUT.TXTOUTPUT.TXT
13
1 2 3
2
1 2
25
2 1 5 9 6
2
2 3

Система оценки

Решения, работающие только при N ≤ 1000, будут оцениваться в 40 баллов.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 2022 / 2023 7-8 классы
 2022 / 2023 9-11 классы
 2023 / 2024 7-8 классы
 2023 / 2024 9-11 классы
 2024 / 2025 7-8 классы
 2024 / 2025 9-11 классы
 A. Принцип Дирихле
 B. Красивая дата
 C. Максимальный прямоугольник
 D. Лексикографически минимальное число
 E. Полка с книгами
 F. Миссия невыполнима

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru