<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

416. Optimal Dartboard
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A dartboard is a disc divided into n segments, with each segment labeled with a distinct positive integer between 1 and n. That integer indicates the score for hitting the segment. To make the game more interesting, the arrangement of numbers is chosen in such a way that the risk is maximized. The risk is estimated based on the differences in scores of adjacent segments.

We're studying the following 'double-layered' structure of segments in this problem:



I.e., n is always even, and we split the disc into two layers of  parts along the circumference. We enumerate the segments in the following manner: the first segment is some outer segment, the second segment is the corresponding inner segment, the third segment is some adjacent outer segment, etc. An example of this enumeration is shown on the picture above.

The total risk is defined as the sum of squared differences between the scores of adjacent segments. If the value assigned to segment i is ai, then the risk is:

R=∑i=1n(ai-ai+2)2+∑i=1n/2(a2i-1-a2i)2

(we assume an+1=a1 and an+2=a2 in this formula).

You are to place the numbers from 1 through n into the segments in such a way that the total risk R is maximized.

Input
The input file contains an even integer number n (6 ≤ n ≤ 100).

Output
Output n integer numbers: a1, a2,..., an, separated with single spaces. In case there are several possible solutions, output any.

Example(s)
sample input
sample output
10
2 9 7 4 6 5 3 8 10 1

<|response|>
## 1) Abridged problem statement (concise)

Given an even integer \(n\) (\(6 \le n \le 100\)), place numbers \(1..n\) into \(n\) segments of a “double-layer” circular dartboard. Segments are indexed:

outer, inner, outer, inner, … around the circle.

Let the permutation be \(a_1,\dots,a_n\) (cyclic: \(a_{n+1}=a_1,\ a_{n+2}=a_2\)). Define

\[
R=\sum_{i=1}^{n}(a_i-a_{i+2})^2\;+\;\sum_{i=1}^{n/2}(a_{2i-1}-a_{2i})^2.
\]

Output any permutation maximizing \(R\).

---

## 2) Key observations

1. **Two independent “adjacency” types**
   - The term \((a_i-a_{i+2})^2\) connects positions 2 apart, so it compares **outer-to-next-outer** and **inner-to-next-inner** (two separate rings).
   - The term \((a_{2i-1}-a_{2i})^2\) compares **outer vs inner** on the same spoke.

2. **Squared differences favor extremes**
   Large gaps are disproportionately valuable: pairing small with large is best.

3. **Spokes should pair extremes**
   To maximize \(\sum (a_{2i-1}-a_{2i})^2\), each spoke should contain an extreme pair:
   \[
   (1,n), (2,n-1), (3,n-2), \dots
   \]

4. **But we must also maximize both rings**
   If all small numbers land on the outer ring in increasing order (1,2,3,...) then outer ring differences are tiny → bad.
   So we must **arrange the extreme pairs around the circle** so that:
   - outer ring alternates low/high as much as possible,
   - inner ring also alternates low/high.

---

## 3) Full solution approach

### Step A: Build extreme pairs for spokes
Create pairs:
\[
(1,n), (2,n-1), \dots, \left(\frac n2,\frac n2+1\right).
\]
Putting each pair on positions \((2i-1, 2i)\) guarantees very large spoke differences.

### Step B: Arrange pairs around the circle to “oscillate” on both rings
We construct the final sequence using a deque/list and insert each next pair to the **front** or **back**, sometimes swapping the order inside the pair. A repeating 4-step pattern works well:

Start with:
- `ans = [1, n]`

For remaining pairs \((x,y)\) in order \((2,n-1),(3,n-2),...\), for `idx = 0..(n/2-2)`:

- `idx % 4 == 0`: push to **back** as `(y, x)`
- `idx % 4 == 1`: push to **front** as `(y, x)`
- `idx % 4 == 2`: push to **back** as `(x, y)`
- `idx % 4 == 3`: push to **front** as `(x, y)`

This “weaves” small and large values across both rings, increasing \((a_i-a_{i+2})^2\) while preserving maximal spoke gaps.

### Complexity
- Time: \(O(n)\)
- Memory: \(O(n)\)

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n; // even, 6..100

    // We will create "extreme" spoke pairs:
    // (1,n), (2,n-1), (3,n-2), ...
    // Fix the first pair (1,n) in the answer to start.
    list<int> ans = {1, n};

    // Remaining pairs start from i=2 up to i=n/2
    // Pair is (i, n-i+1)
    vector<pair<int,int>> pairs;
    for (int i = 2; 2 * i <= n; i++) {
        pairs.push_back({i, n - i + 1});
    }

    // Place each pair around the circle using a 4-step pattern.
    // The goal is to alternate low/high on both outer ring (odd positions)
    // and inner ring (even positions), thus increasing (a_i - a_{i+2})^2.
    for (int idx = 0; idx < (int)pairs.size(); idx++) {
        int x = pairs[idx].first;
        int y = pairs[idx].second;
        int op = idx % 4;

        if (op == 0) {
            // back, inverted => ... y, x
            ans.push_back(y);
            ans.push_back(x);
        } else if (op == 1) {
            // front, but inserting to front reverses order of operations.
            // We want front: y, x, ...
            // So push_front(x) then push_front(y).
            ans.push_front(x);
            ans.push_front(y);
        } else if (op == 2) {
            // back, normal => ... x, y
            ans.push_back(x);
            ans.push_back(y);
        } else { // op == 3
            // front, want x, y, ...
            // push_front(y) then push_front(x)
            ans.push_front(y);
            ans.push_front(x);
        }
    }

    // Output permutation
    bool first = true;
    for (int v : ans) {
        if (!first) cout << ' ';
        first = false;
        cout << v;
    }
    cout << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
from collections import deque

def solve() -> None:
    n = int(sys.stdin.readline().strip())

    # Start with the first extreme pair on a spoke: (1, n)
    # This means a1=1 (outer), a2=n (inner) for that spoke.
    ans = deque([1, n])

    # Remaining extreme pairs: (2, n-1), (3, n-2), ..., (n/2, n/2+1)
    pairs = [(i, n - i + 1) for i in range(2, n // 2 + 1)]

    # Insert pairs in a repeating 4-operation pattern to make both rings
    # alternate between low and high values, boosting (a_i - a_{i+2})^2.
    for idx, (x, y) in enumerate(pairs):
        op = idx % 4
        if op == 0:
            # back, inverted: y, x
            ans.append(y)
            ans.append(x)
        elif op == 1:
            # front: y, x
            # appendleft reverses, so do x then y
            ans.appendleft(x)
            ans.appendleft(y)
        elif op == 2:
            # back, normal: x, y
            ans.append(x)
            ans.append(y)
        else:  # op == 3
            # front: x, y
            # appendleft reverses, so do y then x
            ans.appendleft(y)
            ans.appendleft(x)

    print(" ".join(map(str, ans)))

if __name__ == "__main__":
    solve()
```

This construction is fast, simple, and accepted for the given constraints; if multiple optimal permutations exist, any one of them is valid.