|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.
A permutation is a sequence of N different numbers from 1 to N.
For example, there are six permutations for N = 3:
- 1, 2, 3
- 1, 3, 2
- 2, 1, 3
- 2, 3, 1
- 3, 1, 2
- 3, 2, 1
We say that a permutation is interesting if it does not contain 3 numbers that
make an arithmetic progression. E.g., all the permutations for
N = 3 above are interesting, except the first and the last. On the
contrary, permutation 5, 1, 2, 4, 3 is not interesting, since it contains
numbers 1, 2, 3 that make an arithmetic progression. It does not matter
that there is number 4 between 2 and 3. The ascending or descending order
of numbers is all that matters. Also you can take 5, 4, 3, since these
numbers also make the arithmetic progression.
Your task is to find at least one interesting permutation for number
N, if there exists any.
Input
The first line contains a single integer N (3 ≤ N ≤ 100000).
Output
The first line of output should contain the word "NO" (capital letters
and no quotes) if there are no interesting permutations for N.
Otherwise, the first line of output should contain "YES" (capital letters
and no quotes), and the second line should contain the permutation itself.
Numbers in permutation should be separated by spaces. If there are several
solutions, you may output any of them.
|
Input 1
|
Output 1
|
3
|
YES
3 1 2
|
|
Input 2
|
Output 2
|
5
|
YES
4 2 3 1 5
|
Для отправки решений необходимо выполнить вход.
|