수열 만들기

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

요약

첫 항과 마지막 항이 1이고 가운데 항은 1부터 N까지이며, 마지막 항을 제외한 인접한 두 항의 쌍이 모두 서로 다른 가장 긴 수열을 만든다.

문제

다음 성질을 만족하는 가장 긴 수열 $A$ 를 출력한다.

$A$ 의 첫 수와 마지막 수는 모두 1이고, 나머지 수는 1 이상 $N$ 이하인 정수이다.
$1 \le i < j < |A|$ 일 때, $A_i \neq A_j$ 와 $A_{i+1} \neq A_{j+1}$ 중 적어도 하나는 성립한다.

정수 $N$ 이 주어진다. ( $2 \le N \le 1000$ )

문제 지문의 조건을 만족하는 가장 긴 수열을 $A$ 라 하자.

첫째 줄에는 $A$ 의 길이를 출력한다.

둘째 줄에는 $A$ 의 원소를 출력한다. 이러한 수열이 여러 개면 아무거나 출력한다.

수열의 원소는 한 줄에 모두 출력하고, 수 사이에는 공백을 출력한다.