Задача B. Кубики ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Когда Вова был маленьким, родители подарили ему набор из n кубиков, на каждом из которых написано некоторое натуральное число. В этом наборе нет двух кубиков, на которых написаны одинаковые числа.

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

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

Зайдя в комнату, Вова сразу почуял неладное. Допросив Олю, он узнал как получилось так, что кубики перемешались. И тут Вову заинтересовало — может ли он выяснить каким количеством кубиков играл Петя (при этом Оля играла оставшимися)? Он поручил вам решить эту задачу!

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

Формат входного файла

Первая строка входного файла содержит единственное число n (1 ≤ n ≤ 300000) — количество кубиков у Вовы.

Вторая строка содержит n целых чисел a_i (1 ≤ a_i ≤ 10⁹) — числа, написанные на кубиках, выложенных в порядке слева направо в тот момент, когда Вова вернулся домой. Все a_i различны.

Формат выходного файла

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

Примеры тестов

3
1 2 3

2
1 2 

5
2 1 5 9 6

2
2 3