Последовательность - 2

Вася написал на доске n целых чисел a_i и ушел. Пришел Петя и, увидев Васину последовательность, решил ее немного изменить. Для этого он решил, что может стирать с доски лишь те числа, у которых имеются слева и справа элементы, превосходящие их. Формально, Петя может стереть число a_k, если существуют значения a_i и a_j такие, что a_i > a_k и a_j > a_k и i < k < j. Когда на доске не осталось чисел, которые мог стереть Петя, он ушел.

Пришел Вася и очень удивился увиденному. Напишите программу, которая выводит последовательность, которую увидел Вася.

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

Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 10 000) - количество чисел. Следующая строка содержит n разделенных пробелом целых чисел a_i (-10⁶ ≤ a_i ≤ 10⁶) - записанные на доске числа.

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

В первой строке выходного файла OUTPUT.TXT выведите целое число k - количество оставшихся на доске чисел. На следующей строке выведите k чисел b_i - оставшиеся на доске числа.

Пример

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

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