Permutation with Prescribed Interval Range Sum

Given a positive integer \(n\), construct a permutation \(P = [p_1, p_2, \dots, p_n]\) of \(\{1, 2, \dots, n\}\) such that the sum of the range of every contiguous subarray equals \(\sum_{i=1}^{n-1} i^2\).

A contiguous subarray \(P[l \ldots r]\) has a range defined as the difference between its maximum and minimum values, i.e.,

[ \text{range}(P[l \ldots r]) = \max(p_l, p_{l+1}, \dots, p_r) - \min(p_l, p_{l+1}, \dots, p_r) ]

Your task is to output any such permutation that satisfies the condition.

It can be shown that one valid solution is to output a permutation that alternates between the largest and smallest remaining elements. For example, for \(n = 3\), one valid output is [3, 1, 2], and for \(n = 4\), one valid output is [4, 1, 3, 2].

inputFormat

The input consists of a single positive integer \(n\) (\(1 \leq n \leq 10^5\)).

Input is given in a single line.

outputFormat

Output a permutation of \(\{1, 2, \dots, n\}\) that satisfies the condition. The numbers should be separated by spaces.

sample

1

1