원소 교환

면접 대비

시간 제한1초메모리 제한1024 MB

요약

길이 N인 수열 A를 원소 교환으로 재배열해 모든 위치의 값이 원래 값과 달라지게 하거나, 불가능하면 -1을 출력합니다.

문제

길이가 $N$ 인 정수로 이루어진 수열 $A_1, A_2, \cdots, A_N$ 이 주어진다. 이 수열의 원소 중에서 서로 다른 두 원소를 골라 위치를 바꾸는 연산을 원하는 만큼 시행하여 새로운 수열 $B_1, B_2, \cdots, B_N$ 을 만들려고 한다.

모든 $i$ ( $1 \le i \le N$ )에 대해 $A_i \ne B_i$ 인 수열 $B_1, B_2, \cdots, B_N$ 을 만들 수 있을까?

첫째 줄에 $N$ 이 주어진다. ( $1 \le N \le 5\,000$ )

둘째 줄에 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$ 이 주어진다. ( $1 \le A_i \le 100\,000$ )

조건을 만족하는 수열 $B_1, B_2, \cdots, B_N$ 을 만들 수 없다면 첫째 줄에 -1을 출력한다.

만들 수 있다면 첫째 줄에 그러한 수열 $B_1, B_2, \cdots, B_N$ 을 아무거나 하나 출력한다.