Сортировка за линию?

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

К сожалению, в программе робота, который отвечает за сортировку, произошёл сбой и теперь он способен сделать только n шагов. На i-м шаге он может либо ничего не делать, либо перевернуть отрезок [1..i], то есть изменить порядок предметов на позициях от 1 до i (включительно) на противоположный.

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

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

Первая строка входного файла INPUT.TXT содержит целое число n — количество предметов (1 ≤ n ≤ 2×10⁵).

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

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

В выходной файл OUTPUT.TXT выведите «NO», если отсортировать предметы невозможно. Иначе, в первой строке выведите «YES», а во вторую — n чисел r_i, разделенных пробелом. Если на i-м шаге нужно делать переворот, то r_i=1, а иначе r_i=0. Разрешается выводить любой подходящий ответ.

Примеры

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

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