수열 만들기

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

요약

N이 주어질 때, 원소가 0 이상 N 이하인 수열 A를 만들어 합이 N의 배수인 구간이 정확히 N개가 되게 합니다. 불가능하면 -1을 출력합니다.

난이도: 보통10점 중 5점
유형: 누적 합, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

수열의 길이 $N$ 이 주어졌을 때, 아래 조건을 만족하는 수열 $A$ 를 구해보자. 단, 수열의 원소는 $N$ 보다 작거나 같은 음이 아닌 정수여야 한다. 합 $A_l + A_{l+1} + \cdots + A_{r-1} + A_r$ 이 $N$ 의 배수인 구간 $[l, r]$ $(1 \leq l \leq r \leq N)$ 의 개수가 정확히 $N$ 개이다.

입력

첫째 줄에 수열의 길이 $N$ 이 주어진다. $(1 \leq N \leq 200,000)$

출력

조건을 만족하는 수열의 원소를 순서대로 공백으로 구분하여 출력한다. 조건을 만족하는 수열이 존재하지 않으면 -1을 출력한다. 조건을 만족하는 수열이 여러 가지라면 아무거나 출력한다.

예제2

예제 1
입력
```
3
```
예상 출력
```
2 1 3
```
예제 2
입력
```
5
```
예상 출력
```
-1
```