HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Arithmetic > problem:


50267 - Interesting permutations

Guest
• Discussion of problem (1)

Section problems

• 50243 - Sum of digits
• 50241 - Greatest common divisor
• 50240 - The numbers that are divisi...
• 50242 - Numbers whose sum of the...
• 50248 - Power of two
• 50641 - Strong Prime Power
• 50249 - Ladders
• 50247 - Missing numbers
• 50267 - Interesting permutations
• 50640 - Cubes
• 50377 - kth Permutation
• 50341 - Separate Into Digits
• 50424 - Area
• 50335 - Five Math Operators
• 50299 - Median
• 50301 - Fractions to Decimals
• 50304 - Number Pattern

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Автор: Павел Кузнецов, ПГУ.

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

Для отправки решений необходимо выполнить вход.

www.contester.ru