Рус Uzb Eng

0022. Парад
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт


Генералу Тупикову пришла в голову гениальная идея эффектного шоу во время проведения парада в честь пятидесятилетия победы в маленькой победоносной войне Флатландии над Берляндией.
В параде примет участие n солдат. Солдаты, выстроенные в колонну по одному, выйдут на главную площадь.
Затем, по команде генерала, некоторые солдаты сделают шаг влево, а остальные солдаты — шаг вправо. В результате солдаты, сделавшие шаг влево, должны оказаться упорядочены по возрастанию роста, а сделавшие шаг вправо — по убыванию.
Генерал приказал немедленно принести ему список солдат, которые примут участие в параде, чтобы определить, в каком порядке им следует построиться, кому сделать шаг влево, а кому — вправо. Однако выяснилось, что репетиции парада продолжаются уже несколько месяцев и солдаты знают, в каком порядке они должны выйти на площадь.
Эта новость слегка огорчила генерала, но он не упал духом. Он выяснил рост всех солдат, которые примут участие в параде, и теперь хочет разбить всех солдат на два непустых множества: тех кто сделает шаг влево и тех, кто сделает шаг вправо. Сделавшие шаг влево должны оказаться упорядочены по возрастанию роста, а сделавшие шаг вправо — по убыванию.
Помогите генералу составить сценарий парада, выясните, кому из солдат надо отдать команду сделать шаг влево.
Остальные солдаты сделают шаг вправо. Хотя бы один солдат должен сделать шаг влево, и хотя бы один солдат должен сделать шаг вправо.

Входные данные:
В первой строке задано целое число n (2 < n < 100 000) — количество солдат. Во второй строке задано n целых положительных чисел a1, a2,... ,an — рост солдат (1 < ai < 109). Рост солдат приведен в порядке, в котором они выйдут на площадь.

Выходные данные:
В первой строке выведите k — количество солдат, которым надо сделать шаг влево (1 < k < n — 1). В второй строке выходного файла выведите k целых чисел b1,b2, … , bk — номера солдат, которым надо сделать шаг влево (1 < b12 < ... k < n). Рост этих солдат должен строго возрастать, а рост оставшихся солдат должен строго убывать. Если решений несколько, выведите любое.
В случае, если решения нет, в единственной строке выходного файла выведите «Impossible».

Пример ввода Пример вывода
6
6 1 4 3 2 5
6
1 3 2 4 6 5
3
1 1 1
3
2 4 6
Impossible


Impossible
Область:
Источник задачи: XII ВКОШП 2011 Финал

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.