#489 Median 2

Loading problem...

Preparing the statement, recent submissions, and submit form.

#489 Median 2

Authors: pk661

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

Statement language

For a sequence $S$ of length $M$ , let $X_1 \le X_2 \le \cdots \le X_M$ be the result of sorting $S$ in increasing order. The median of $S$ is defined as

\operatorname{median}(S)= \begin{cases} X_{(M+1)/2} & (M\text{ is odd}),\\ (X_{M/2}+X_{M/2+1})/2 & (M\text{ is even}). \end{cases}

You are given a positive integer $N$ and two integer sequences $A=(A_1,A_2,\cdots,A_N)$ and of length .

Find a permutation $(P_1, P_2, \cdots, P_N)$ of such that the following holds for every :

\operatorname{median}(P_1,P_2,\cdots,P_i)=\frac{A_i}{2},\quad \operatorname{median}(P_i,P_{i+1},\cdots,P_N)=\frac{B_i}{2}.

If no such permutation exists, print $-1$ .

Input

The input is given from Standard Input in the following format:

$N$ $A_1\ A_2\ \cdots\ A_N$

Output

If no permutation satisfies the conditions, print $-1$ .

Otherwise, print one such permutation in the following format:

$P_1\ P_2\ \cdots\ P_N$

Constraints

$1\le N\le 200\,000$ .
$2\le A_i\le 2N$ ().

Subtasks

#	Score	Constraints
1	7	$N\le 10$ .
2	22	$N$ is even. $\|A_{2k}-A_{2k-1}\|=1$ for every integer ().

Samples

Sample 1

Input

5
6 8 8 7 6
6 6 4 3 4

Output

3 5 4 1 2

Sample 2

Input

2
2 3
3 2

Output

-1

Editorial

View editorial