30708번 - 업&다운 스페셜 저지

문제

당신의 손에 카드가 $N$장 있고, 각 카드에는 양의 정수가 하나씩 쓰여 있다. 각 $i(1\leq i\leq N)$에 대해 $i$번째 카드에는 양의 정수 $X_i$가 쓰여 있다. 같은 숫가 적힌 카드가 여러 장 있을 수도 있다.

당신은 손에 있는 카드를 다음과 같은 규칙에 따라 탁자에 모두 놓아야 한다.

탁자에는 카드를 한 번에 한 장씩만 놓을 수 있다. 첫 카드는 아무거나 놓을 수 있지만, 두 번째 카드부터는 바로 이전에 놓은 카드에 적힌 숫보다 수가 1ドル$만큼 크거나 작은 카드만 놓을 수 있다. 가령, 처음에 3ドル$이 적힌 카드를 놓았으면 그다음에는 2ドル$ 또는 4ドル$가 적힌 카드를 놓을 수 있고, 그 외의 카드는 놓지 못한다.

당신이 손에 든 카드의 정보가 주어졌을 때, 이 카드들을 주어진 규칙을 지키면서 탁자에 모두 놓을 수 있는 방법을 찾아라.

입력

첫째 줄에는 카드의 수 $N$이 정수로 주어진다. (1ドル\leq N\leq 100,000円$)

둘째 줄에는 각 카드에 적힌 수 $X_1, X_2, \cdots , X_N$이 공백으로 구분되어 주어진다.(1ドル\leq X_i\leq 100,000円$)

출력

주어진 카드를 규칙을 지키면서 탁자에 모두 놓는 방법이 존재한다면, 카드를 내는 순서대로 총 $N$개의 정수 $Y_1,Y_2,\cdots ,Y_N$을 공백으로 구분하여 출력한다. $Y_i(1\leq i\leq N)$는 $i$번째로 탁자에 놓을 카드에 적힌 정수를 의미하며, $X_1,X_2,\cdots ,X_N$을 오름차순 정렬한 결과와 $Y_1,Y_2,\cdots ,Y_N$을 오름차순 정렬한 결과는 같아야 한다. 가능한 방법이 여러 가지라면 그 중 아무거나 하나를 출력한다.

만일 카드를 탁자에 모두 놓는 것이 불가능할 경우 -1을 출력한다.

제한

힌트