순열 복원

크리스토퍼는 오늘 학교에서 수열과 순열을 배웠다. $1$부터 $n$까지의 수가 각각 정확히 한 번씩 나타나는 수열 $a_1, \ldots, a_n$을 순열이라고 한다.

크리스토퍼가 특히 마음에 들어 한 정의는 다음과 같다.

• 순열 $\langle a_1, a_2, \ldots, a_n \rangle$에서 위치 $i$의 하강은 $a_i > a_{i+1}$인 경우를 말한다.
• 순열 $\langle a_1, a_2, \ldots, a_n \rangle$에서 위치 $i$의 고정점은 $a_i = i$를 만족하는 원소 $a_i$를 말한다.

크리스토퍼는 직접 순열을 만들고 이를 로빈 순열이라고 불렀다. $1$부터 $2n$까지의 수로 이루어진 순열 $A = \langle a_1, a_2, \ldots, a_{2n} \rangle$이 다음 두 조건을 모두 만족하면 로빈 순열이다.

• $A$의 하강은 정확히 $n$개이며, 모든 하강은 홀수 위치에 있다. 즉, 모든 $i$에 대해 $a_{2i-1} > a_{2i} < a_{2i+1}$이다.
• $A$의 고정점은 정확히 $n$개이다.

예를 들어 $\langle 3, 2, 6, 4, 5, 1 \rangle$은 로빈 순열이다.

크리스토퍼는 이 발견을 토끼에게 알려 주었다. 로빈 순열을 알게 된 토끼는 다음 변환을 떠올렸다. 수열에서 고정점을 모두 지운 뒤, 남은 수 각각을 남은 수열에서 그 수 이하인 원소의 개수로 바꾼다. 예를 들어 $\langle 3, 2, 6, 4, 5, 1 \rangle \to \langle 3, 6, 1 \rangle \to \langle 2, 3, 1 \rangle$이다.

이제 크리스토퍼는 변환된 순열이 주어졌을 때, 그 순열로 변환되는 로빈 순열을 찾으려 한다.

첫 줄에 변환된 순열의 원소 개수 $n$이 주어진다 ($1 \le n \le 100\,000$). 둘째 줄에는 변환된 순열을 이루는 $n$개의 자연수가 주어진다.

해가 없으면 첫 줄에 $-1$을 출력한다. 로빈 순열이 존재하면 그중 하나를 출력한다. 답이 여러 개이면 그중 아무 로빈 순열이나 출력해도 된다.