E - Young Maids

Contest Duration: 2017-08-06(Sun) 12:00 - 2017-08-06(Sun) 13:40 (local time) (100 minutes) Back to Home

E - Young Maids Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $800$ 点

問題文

$N$ を正の偶数とします。

$(1, 2, ..., N)$ の順列 $p = (p_1, p_2, ..., p_N)$ があります。すぬけ君は、次の手続きによって $(1, 2, ..., N)$ の順列 $q$ を作ろうとしています。

まず、空の数列 $q$ を用意します。 $p$ が空になるまで、次の操作を繰り返します。

$p$ の隣り合う $2$ つの要素を選び、順に $x$ , $y$ とする。 $x$ , $y$ を $p$ から取り除き (このとき、 $p$ は $2$ だけ短くなる)、 $x$ , $y$ をこの順のまま $q$ の先頭へ追加する。

$p$ が空になったとき、 $q$ は $(1, 2, ..., N)$ の順列になっています。

辞書順で最小の $q$ を求めてください。

制約

$N$ は偶数である。
$2 ≤ N ≤ 2 × 10^5$
$p$ は $(1, 2, ..., N)$ の順列である。

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $p_1$   $p_2$   $...$   $p_N$

出力

辞書順で最小の $q$ を空白区切りで出力せよ。

入力例 1Copy

Copy

4
3 2 4 1

出力例 1Copy

Copy

3 1 2 4

次の順に操作を行えばよいです。

$p$	$q$
$(3, 2, 4, 1)$	$()$
↓	↓
$(3, 1)$	$(2, 4)$
↓	↓
$()$	$(3, 1, 2, 4)$

入力例 2Copy

Copy

2
1 2

出力例 2Copy

Copy

1 2

入力例 3Copy

Copy

8
4 6 3 2 8 5 7 1

出力例 3Copy

Copy

3 1 2 7 4 6 8 5

次の順に操作を行えばよいです。

$p$	$q$
$(4, 6, 3, 2, 8, 5, 7, 1)$	$()$
↓	↓
$(4, 6, 3, 2, 7, 1)$	$(8, 5)$
↓	↓
$(3, 2, 7, 1)$	$(4, 6, 8, 5)$
↓	↓
$(3, 1)$	$(2, 7, 4, 6, 8, 5)$
↓	↓
$()$	$(3, 1, 2, 7, 4, 6, 8, 5)$

Score : $800$ points

Problem Statement

Let $N$ be a positive even number.

We have a permutation of $(1, 2, ..., N)$ , $p = (p_1, p_2, ..., p_N)$ . Snuke is constructing another permutation of $(1, 2, ..., N)$ , $q$ , following the procedure below.

First, let $q$ be an empty sequence. Then, perform the following operation until $p$ becomes empty:

Select two adjacent elements in $p$ , and call them $x$ and $y$ in order. Remove $x$ and $y$ from $p$ (reducing the length of $p$ by $2$ ), and insert $x$ and $y$ , preserving the original order, at the beginning of $q$ .

When $p$ becomes empty, $q$ will be a permutation of $(1, 2, ..., N)$ .

Find the lexicographically smallest permutation that can be obtained as $q$ .

Constraints

$N$ is an even number.
$2 ≤ N ≤ 2 × 10^5$
$p$ is a permutation of $(1, 2, ..., N)$ .

Input

Input is given from Standard Input in the following format:

 $N$ 
 $p_1$   $p_2$   $...$   $p_N$

Output

Print the lexicographically smallest permutation, with spaces in between.

Sample Input 1Copy

Copy

4
3 2 4 1

Sample Output 1Copy

Copy

3 1 2 4

The solution above is obtained as follows:

$p$	$q$
$(3, 2, 4, 1)$	$()$
↓	↓
$(3, 1)$	$(2, 4)$
↓	↓
$()$	$(3, 1, 2, 4)$

Sample Input 2Copy

Copy

2
1 2

Sample Output 2Copy

Copy

1 2

Sample Input 3Copy

Copy

8
4 6 3 2 8 5 7 1

Sample Output 3Copy

Copy

3 1 2 7 4 6 8 5

The solution above is obtained as follows:

$p$	$q$
$(4, 6, 3, 2, 8, 5, 7, 1)$	$()$
↓	↓
$(4, 6, 3, 2, 7, 1)$	$(8, 5)$
↓	↓
$(3, 2, 7, 1)$	$(4, 6, 8, 5)$
↓	↓
$(3, 1)$	$(2, 7, 4, 6, 8, 5)$
↓	↓
$()$	$(3, 1, 2, 7, 4, 6, 8, 5)$