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