Beautiful Permutation

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

요약

순열 a가 0부터 n-1까지의 값을 가지면서 |a_i - i|도 0부터 n-1까지의 순열이 되는 a를 구성하거나, 존재하지 않으면 NO를 출력한다.

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

문제

A permutation $a\_0, a\_1, \ldots, a\_{n - 1}$ of $0, 1, \ldots, n - 1$ is said to be beautiful if the sequence $b\_0, \ldots, b\_{n - 1}$ defined as $b\_i = |a\_i - i|$ is also a permutation of $0, \ldots, n - 1$ .

Given $n$ , construct a beautiful permutation of $n$ elements or determine that it does not exist.

입력

The first line contains a single integer $n$ ( $1 \leq n \leq 10^6$ ): the size of the permutation.

출력

If there is no beautiful permutation of $n$ elements, output a single line with the word "NO".

Otherwise, on the first line, print "YES", and on the second line, print $n$ space-separated integers $a\_0, \ldots, a\_{n-1}$ : the beautiful permutation. If there are multiple beautiful permutations, print any one of them.

예제3

예제 1
입력
```
4
```
예상 출력
```
YES
3 0 2 1
```
예제 2
입력
```
3
```
예상 출력
```
NO
```
예제 3
입력
```
1
```
예상 출력
```
YES
0
```