405187: GYM101821 B LIS vs. LDS

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. LIS vs. LDStime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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.

ExamplesInput
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.

加入题单

上一题 下一题 算法标签: