ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1965. Саженцы груши

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Когда Вова шёл по одной из центральных улиц Шэньчжэня, он обратил внимание на саженцы грушевых деревьев, растущие вдоль тротуара. К каждому саженцу была прикреплена табличка, на которой было написано некоторое число. Обойдя все n саженцев, Вова обнаружил, что числа на табличках попарно различны и лежат в пределах от 1 до n. Очевидно, сначала предполагалось посадить саженцы в указанном порядке, но сейчас они были перемешаны странным образом: после шестого шёл четвёртый, затем третий, затем пятый...
Рядом стояла тележка с мороженым. Мороженщик, заметив, что Вова с недоумением разглядывает саженцы груши, рассказал ему, что видел, как неделю назад их высаживали в землю. Бригадир поручил это дело двум рабочим, сказав, чтобы те посадили саженцы по порядку номеров, указанных на табличках. После этого бригадир уехал, а рабочие поделили между собой саженцы и приступили к работе. Поскольку бригадир не уточнил, по возрастанию или убыванию должны следовать номера на табличках, каждый рабочий принял на этот счёт самостоятельное решение, не посоветовавшись с напарником. Оба рабочих, сажая деревья, следовали в одном направлении с одного и того же конца улицы.
Рассмотрим пример. Пусть n = 8, и рабочие поделили саженцы так, что первому достались саженцы с номерами 1, 4 и 5, а второму — 2, 3, 6, 7 и 8. В результате получилась такая последовательность номеров на табличках: 8, 7, 1, 6, 4, 3, 5, 2 (первый сажал деревья по возрастанию номеров, а второй — по убыванию).
Вова записал все номера на табличках в том порядке, в котором деревья были посажены, и захотел определить, какие саженцы были высажены первым рабочим, а какие — вторым. Помогите ему сделать это.

Исходные данные

В первой строке записано целое число n — количество саженцев (3 ≤ n ≤ 100 000). Во второй строке записаны n различных целых чисел в пределах от 1 до n — перестановка номеров, записанная Вовой.

Результат

Выведите в первой строке два целых числа в пределах от 1 до (n − 1) — сколько деревьев посадил первый и второй рабочий соответственно. Во второй строке выведите номера деревьев, посаженных первым рабочим, в третьей — номера деревьев, посаженных вторым рабочим. Номера должны следовать в том порядке, в котором рабочий сажал эти деревья. Если существует несколько решений, можно вывести любое из них. Если решения не существует, выведите «Fail».

Примеры

исходные данныерезультат
8
8 7 1 6 4 3 5 2
3 5
1 4 5
8 7 6 3 2
6
3 5 1 2 6 4
3 3
3 5 6
1 2 4
6
3 5 2 1 6 4
Fail
Автор задачи: Сергей Пупырев
Источник задачи: Открытое личное первенство УрФУ по программированию 2013