34549번 - 도치균형의 배열 스페셜 저지

문제

홍익대의 도사는 도술로 도치균형의 배열을 만든다.

크기가 $N$인 배열 $A$에서, 각 위치 $i$에 대해 아래를 정의하자.

• $D[i] = \bigl|\{,円 j \in \{i+1,\dots,N\}: A[i] > A[j] ,円\}\bigr|$ 뒤쪽과 엄밀히 내림차순을 이루는 쌍의 개수
• $U[i] = \bigl|\{,円 j \in \{i+1,\dots,N\}: A[i] < A[j] ,円\}\bigr|$ 뒤쪽과 엄밀히 오름차순을 이루는 쌍의 개수

배열 $A$가 다음을 만족하면 도치균형의 배열(Inversion Balance Array)이라 부른다.

$$\sum_{i=1}^{N} D[i] = \sum_{i=1}^{N} U[i].$$

즉, 배열 전체에서 엄밀히 내림차순인 쌍의 개수와 엄밀히 오름차순인 쌍의 개수가 서로 같다는 뜻이다. 같은 값인 쌍은 위 정의에서 세지 않는다.

도사의 도치균형의 배열을 보며 와우가 물었다.

"모든 배열이 같은 값으로만 구성되면 도치균형의 배열이네요. 너무 시시한데요?"

그 말을 듣고 도사는 다음과 같이 되물었다.

"그럼 1ドル$부터 $M$까지의 자연수를 한 번 이상 사용하되, 배열의 크기는 2ドルM$이하인 도치균형의 배열도 만들 수 있겠느냐?"

우리는 와우를 도와, 1ドル$부터 $M$까지의 수가 각각 최소 한번씩은 등장하고, 크기가 2ドルM$이하인 도치균형의 배열을 하나 만들어보자.

문제에서 주어지는 $M$에 대해 조건을 만족하는 도치균형의 배열이 항상 존재함은 증명할 수 있다.

입력

정수 $M$이 주어진다. (1ドル \le M \le 1000$)

출력

문제의 조건을 만족하는 도치균형의 배열을 한 줄에 출력한다.

출력하는 도치균형의 배열의 원소는 10억 이하의 자연수이다.

제한

노트