Maximise the squared difference Consider a permutation of the integer values from 1 to N. E.g. this example for N = 4:

[1, 3, 4, 2]


We'll consider this list to be cyclic, such that 1 and 2 are treated as adjacent. One quantity we can compute for such a list is the total squared difference of adjacent values:

(1-3)² + (3-4)² + (4-2)² + (2-1)² = 10


Your task is to find a permutation which maximises this quantity, given a positive integer N. In the case of N = 4 the above example is not optimal (in fact, it's minimal). We can achieve a total squared difference of 18 with the following permutation (as well as several others):

[1, 4, 2, 3]


Your algorithm must run in polynomial time (of N). In particular, you cannot simply compute the total squared difference of all permutations.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Output may be in any convenient, unambiguous, flat list or string format. You may choose to return a list with values from 0 to N-1 instead of 1 to N.

Standard code-golf rules apply.

Test Data

There is a nice analytical solution for this problem. E.g. all valid solutions for N = 10 are equivalent to the following list (up to cyclic shifts and reversal):

[7, 5, 6, 4, 8, 2, 10, 1, 9, 3]


I don't want to reveal too much beyond that (although it's probably enough to figure out the pattern), so instead of giving any more examples, you can check that your results have the following total squared differences for a given N:

N    Total squared difference

1                         0
2                         2
3                         6
4                        18
5                        36
6                        66
7                       106
8                       162
9                       232
10                      322
33                    11936
100                  333202
333                12308236
1000              333332002


This is OEIS entry A064842 (which also contains a reference to a paper with a solution to this challenge if you're stuck).
Jelly, 24 21 15 14 10 9 bytes

RUĖµ«/€ị"


To compute the total squared difference, append µ_ṙ1$²S to the code. Try it online!

Background

One way to generate a permutation with maximized squared difference is to take the integers 1 to n in ascending order, and swap the second from the left with the second from the right, the fourth from the left with the fourth from the right, and so forth until we meet in the middle.

For example, for n = 8, 9 we have

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
  ^   ^ ^   ^            ^   ^   ^   ^


(carets mark integers to be swapped), which results in

1 7 3 5 4 6 2 8        1 8 3 6 5 4 7 2 9


after swapping.

One way to achieve these swaps, independently of the parity of n, is as follows.

Start by writing the integers in ascending order and in descending order, one below the other.

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
8 7 6 5 4 3 2 1        9 8 7 6 5 4 3 2 1


For each pair of integers, compute the minimum of the pair. This gives the distance to the nearest edge, i.e., the index from the left or the right (whichever is lower).

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
8 7 6 5 4 3 2 1        9 8 7 6 5 4 3 2 1

1 2 3 4 4 3 2 1        1 2 3 4 5 4 3 2 1


If the minimum is odd, the integer should stay in its place, so we select the one from the first row; if it is even, the integers should be swapped, so we select the one from the second row.

1   3     6   8        1   3   5   7   9
  7   5 4   2            8   6   4   2


This is the desired output.

How it works

RUĖµ«/€ị"    Main link. Input: n

R            Range. Yields [1, ..., n].
 U           Upend. Yields [n, ..., 1].
  Ė          Enumerate. Yields p := [[1, n], [2, n-1], ... [n-1, 2], [n, 1]].

   µ         Begin a new, monadic chain. Argument: p
     /       Reduce...
      €        each pair of p...
    «          by minimum.
        "    For each minimum and the corresponding pair of p:
       ị       Select the element at that index.
            Indices are modular and 1-based in Jelly, so this selects the first
            element if the minimum is odd, and the second one if it is even.