Linear Algebra: Concepts and Methods

Time limit2sMemory limit1024 MB

Summary

Given N, find a permutation of 1 to N where max minus min is not prime for every contiguous part of length at least 2, or report that none exists.

Level: Medium7 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

Tired of studying linear algebra, the students of KSA came up with the following problem.

Given an integer $N$ , determine whether a sequence satisfying the following conditions exists, and if one exists, find any such sequence.

The sequence is a permutation of length $N$ . That is, each integer from $1$ to $N$ appears exactly once.
For every contiguous subsequence $S$ of the sequence with length at least $2$ , the value of $\max(S) - \min(S)$ is not prime.

A sequence $A$ is called a contiguous subsequence of a sequence $B$ if $A$ can be obtained by removing zero or more elements from the front of $B$ and zero or more elements from the back of $B$ .

However, the KSA students have an illness that prevents them from telling primes apart, so they asked you to solve this problem.

Input

The first line contains an integer $N$ .

Output

On the first line, print YES if a sequence satisfying the conditions exists, and NO otherwise.

If such a sequence $A$ exists, print $N$ integers $A_1, A_2, \cdots, A_N$ separated by spaces on the second line.

If multiple answers exist, you may print any of them.

Constraints

$2\leq N\leq 1000$

Examples2

Example 1
Input
```
5
```
Expected output
```
NO
```
Example 2
Input
```
10
```
Expected output
```
YES
5 4 8 2 10 1 9 3 7 6
```