A - i i's Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

正整数 N が与えられるので、 長さ L \coloneqq N(N+1)/2 の整数列 A = (A_1, A_2, \ldots, A_L) であって、下記の条件をすべて満たすものを 1 つ出力してください。

  • すべての i = 1, 2, \ldots, N について、A は i をちょうど i 個含む。
  • すべての i = 1, 2, \ldots, L について、1 \leq |A_i - A_{i+1}| \leq 2 。ただし、A_{L+1} は A_1 を表す。

なお、本問題の制約下において、上記の条件をすべて満たす長さ L の整数列 A が必ず存在することが証明できます。

制約

  • 3 \leq N \leq 1000
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

A の各要素を下記の形式にしたがって空白区切りで出力せよ。

A_1 A_2 \ldots A_L

なお、問題文中の条件を満たす長さ L の整数列 A が複数存在する場合は、その中のどれを出力しても正解となる。

入力例 1

4

出力例 1

1 3 4 2 4 3 4 2 4 3

整数列 A = (1, 3, 4, 2, 4, 3, 4, 2, 4, 3) は、ちょうど 1 個の 1 、ちょうど 2 個の 2 、ちょうど 3 個の 3 、ちょうど 4 個の 4 を含むため、1 つ目の条件を満たします。 また、下記の通り 2 つ目の条件も満たします。

  • |A_1 - A_2| = |1 - 3| = 2
  • |A_2 - A_3| = |3 - 4| = 1
  • |A_3 - A_4| = |4 - 2| = 2
  • |A_4 - A_5| = |2 - 4| = 2
  • |A_5 - A_6| = |4 - 3| = 1
  • |A_6 - A_7| = |3 - 4| = 1
  • |A_7 - A_8| = |4 - 2| = 2
  • |A_8 - A_9| = |2 - 4| = 2
  • |A_9 - A_{10}| = |4 - 3| = 1
  • |A_{10} - A_1| = |3 - 1| = 2

Score : 400 points

Problem Statement

You are given a positive integer N. Print an integer sequence of length L \coloneqq N(N+1)/2, A = (A_1, A_2, \ldots, A_L), that satisfies all of the following conditions.

  • A contains exactly i occurrences of i for every i = 1, 2, \ldots, N.
  • 1 \leq |A_i - A_{i+1}| \leq 2 for every i = 1, 2, \ldots, L. Here, A_{L+1} means A_1.

It can be proved that, under the Constraints of this problem, there is always an integer sequence A of length L that satisfies all of the above conditions.

Constraints

  • 3 \leq N \leq 1000
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N

Output

Print the elements of A, separated by spaces, in the following format:

A_1 A_2 \ldots A_L

If multiple integer sequences A of length L satisfy the conditions in the problem statement, any one of them is accepted.

Sample Input 1

4

Sample Output 1

1 3 4 2 4 3 4 2 4 3

The integer sequence A = (1, 3, 4, 2, 4, 3, 4, 2, 4, 3) contains exactly one 1, two 2s, three 3s, and four 4s, satisfying the first condition. The second condition is also satisfied, as follows:

  • |A_1 - A_2| = |1 - 3| = 2
  • |A_2 - A_3| = |3 - 4| = 1
  • |A_3 - A_4| = |4 - 2| = 2
  • |A_4 - A_5| = |2 - 4| = 2
  • |A_5 - A_6| = |4 - 3| = 1
  • |A_6 - A_7| = |3 - 4| = 1
  • |A_7 - A_8| = |4 - 2| = 2
  • |A_8 - A_9| = |2 - 4| = 2
  • |A_9 - A_{10}| = |4 - 3| = 1
  • |A_{10} - A_1| = |3 - 1| = 2