B. НВП против НУП
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наибольшей возрастающей подпоследовательностью (НВП) массива a1, ..., an называется последовательность индексов 1 ≤ i1 < ... < ik ≤ n, такая что ai1 < ... < aik и значение k максимально возможное. Наибольшая убывающая подпоследовательность (НУП) определяется аналогично.

В самой свежей задаче для собеседований в Яндекс вам даётся перестановка p = (p1, ..., pn) чисел 1, 2, ..., n, в которой требуется выбрать НВП и НУП не имеющие общих элементов, или определить, что это невозможно сделать. Формально, требуется выбрать две последовательности индексов i1 < ... < ik и j1 < ... < jl, такие что:

  • ai1 < ... < aik;
  • bj1 > ... > bjl;
  • k равняется длине НВП в p;
  • l равняется длине НУП в p,
  • все индексы i1, ..., ik, j1, ..., jl различны.
Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 500 000) — размер перестановки p.

Во второй строке записаны n различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n).

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

Если ответ существует, то выведите его в четырёх строках. В первой строке выведите целое число k — размер НВП в перестановке p. Во второй строке выведите k чисел i1, ..., ik удовлетворяющих условиям 1 ≤ i1 < ... < ik ≤ n и ai1 < ... < aik. В следующих двух строках выведите описание НУП j1, ..., jl в аналогичном формате. Все индексы i1, ..., ik, j1, ..., jl должны быть различны.

Если ответа не существует, то выведите «IMPOSSIBLE» (без кавычек) в единственной строке вывода.

Примеры
Входные данные
4
2 4 1 3
Выходные данные
2
1 4 
2
2 3
Входные данные
4
3 4 1 2
Выходные данные
IMPOSSIBLE
Примечание

Во втором примере длины НВП и НУП равны 2. Приведём список всех возможных НВП: (1, 2), (3, 4) (указаны индексы элементов, а не их значения); также приведём список всех возможных НУП: (1, 3), (1, 4), (2, 3), (2, 4). Каждая НУП пересекается с каждой из НВП хотя бы по одному элементу, следовательно, ответа не существует.