405187: GYM101821 B LIS vs. LDS

A longest increasing subsequence (LIS) of an array a₁, ..., a_n is a sequence of indices 1 ≤ i₁ < ... < i_k ≤ n such that a_i1 < ... < a_ik, and k is largest possible. Longest decreasing subsequence (LDS) can be defined similarly.

A brand new Yandex interview problem asks you to take a permutation p = (p₁, ..., p_n) of numbers 1, 2, ..., n, and find an LIS and an LDS of the permutation that do not share common elements, or report that it is impossible. Formally, you have to find two sequences of indices i₁ < ... < i_k and j₁ < ... < j_l so that:

• a_i1 < ... < a_ik;
• b_j1 > ... > b_jl;
• k is the length of LIS of p;
• l is the length of LDS of p,
• all indices i₁, ..., i_k, j₁, ..., j_l are distinct.

The first line contains an integer n (1 ≤ n ≤ 500 000) — the size of the permutation p.

The second line contains n distinct integers p₁, p₂, ..., p_n (1 ≤ p_i ≤ n).

If an answer exists, print four lines. The first line should contain a single integer k — the size of LIS of the permutation p. The second line should contain k integers i₁, ..., i_k satisftying 1 ≤ i₁ < ... < i_k ≤ n and a_i1 < ... < a_ik. The next two lines should describe an LDS (j₁, ..., j_l) of p in the same format. All indices i₁, ..., i_k, j₁, ..., j_l should be distinct.

If there is no answer, print "texttt{IMPOSSIBLE}" (without the quotes) in the only line of the output.

4
2 4 1 3

2
1 4 
2
2 3 

4
3 4 1 2

IMPOSSIBLE

In the second sample, the length of both LIS and LDS is 2. Here are all possible LIS: (1, 2), (3, 4) (indices of elements are given, not their values); and all possible LDS: (1, 3), (1, 4), (2, 3), (2, 4). Each LIS has a common element with each LDS, hence there is no answer.