Когда Вова шёл по одной из центральных улиц Шэньчжэня, он обратил внимание
на саженцы грушевых деревьев, растущие вдоль тротуара. К каждому саженцу
была прикреплена табличка, на которой было написано некоторое число.
Обойдя все 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