B. LIS vs. LDS
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A longest increasing subsequence (LIS) of an array a1, ..., an is a sequence of indices 1 ≤ i1 < ... < ik ≤ n such that ai1 < ... < aik, 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 = (p1, ..., pn) 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 i1 < ... < ik and j1 < ... < jl so that:

  • ai1 < ... < aik;
  • bj1 > ... > bjl;
  • k is the length of LIS of p;
  • l is the length of LDS of p,
  • all indices i1, ..., ik, j1, ..., jl are distinct.
Input

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

The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n).

Output

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 i1, ..., ik satisftying 1 ≤ i1 < ... < ik ≤ n and ai1 < ... < aik. The next two lines should describe an LDS (j1, ..., jl) of p in the same format. All indices i1, ..., ik, j1, ..., jl should be distinct.

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

Examples
Input
4
2 4 1 3
Output
2
1 4 
2
2 3
Input
4
3 4 1 2
Output
IMPOSSIBLE
Note

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.