선형대수학: 개념과 방법

선형대수학 공부를 하다가 질려버린 KSA 학생들은 아래 문제를 떠올렸다.

정수 $N$이 주어졌을 때, 다음 조건을 만족하는 수열이 존재하는지 판별하고, 그러한 수열이 존재한다면 그중 아무거나 찾아보자.

• 수열은 길이가 $N$인 순열이다. 즉, $1$ 이상 $N$ 이하의 정수들이 정확히 한 번씩 등장한다.
• 수열의 모든 길이가 $2$ 이상인 연속부분수열 $S$에 대해 $\max(S) - \min(S)$의 값은 소수가 아니다.

어떤 수열 $B$의 앞에서부터 $0$개 이상의 원소를 지우고 뒤에서부터 $0$개 이상의 원소를 지워서 수열 $A$를 만들 수 있다면 수열 $A$를 수열 $B$의 연속부분수열이라고 부른다.

그러나 KSA 학생들은 소수를 구별할 수 없는 병에 걸려 당신에게 이 문제를 해결해줄 것을 요청했다.

첫 번째 줄에 정수 $N$이 주어진다.

첫 번째 줄에 조건을 만족하는 수열이 존재한다면 YES, 아니라면 NO를 출력한다.

만약 그러한 수열 $A$가 존재한다면, 두 번째 줄에 $N$개의 정수 $A\_{1}, A\_{2}, \cdots, A\_{N}$을 공백으로 구분하여 출력한다.

정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.

• $2\leq N\leq 1000$