[Question]
  [
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](/questions/tagged/code-golf "show questions tagged '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](https://oeis.org/A064842) (which also contains a reference to a paper with a solution to this challenge if you're stuck).
  
[Answer]
# Jelly, ~~24~~ ~~21~~ ~~15~~ ~~14~~ ~~10~~ 9 bytes
```
RUĖµ«/€ị"
```
To compute the total squared difference, append `µ_ṙ1$²S` to the code. [Try it online!](http://jelly.tryitonline.net/#code=UlXElsK1wqsv4oKs4buLIg&input=&args=MTA)
### 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.
```
[Answer]
# JavaScript (ES6), 52 bytes
```
n=>[...Array(n)].map((_,i)=>(i<n/2|n%2)^i%2?i+1:n-i)
```
*9 bytes saved thanks to @Neil!*
## Explanation
This approach determines the number that should be at index `i` with a length of `n` rather than concatenating the results to an array. This is based on the following observation (using `n = 7` as an example):
* Start with the lowest number on the left and the highest on the right: `[ 1, 7 ]`
* Switch the order so the lowest is on the *right* and the highest is on the left, increment the lowest, decrement the highest, and place them in the middle of the array: `[ 1, 6, 2, 7 ]`
* Repeat until the highest and lowest converge: `[ 1, 6, 3, 4, 5, 2, 7 ]`
The higher and lower numbers can easily be expressed as `n-i` and `i+1` respectively.
```
var solution =
n=>
  [...Array(n)] // create an array of length n
  .map((_,i)=>  // set each value of the array at index i
    (i<n/2      // if we're on the left side,
    |n%2)       // or we're on the right and n is odd, even i => lower, odd i => higher
    ^i%2?       // else even i => higher, odd i => lower
    i+1:n-i
  )
```
```
N = <input type="number" id="input" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>
```
[Answer]
## Python2, ~~105~~ 98 bytes
*7 bytes saved thanks to the comment by @Dennis*
```
n=input()
r=([],[n/2+1])[n%2]
for i in range(n/2,0,-1):k=[n+1-i];r=([i]+r+k,k+r+[i])[i%2]
print r
```
### Edited version 58 bytes
```
lambda n:[(n-i-1,i)[(i+(n,1)[i<n/2])%2]for i in range(n)]
```
I already believed it should be possible to do it as a one-liner, but the logic was too complex for me. Seeing the JavaScript-answer by @user81655 and the lambda-notation in @Dennis Python-answer, I gave it new try.
The condition is equal to
```
if i < n/2:
    i%2 != n%2
else:
    (i+1)%2
```
Unfortunately all the transformation effort saves only ~~one~~ no byte compared to the direct translation `(i<n/2or n%2)!=i%2` of the JavaScript-logic.
[Answer]
# Python, ~~51~~ 49 bytes
```
lambda n:[(i^min(i,~i%n)%-2)%n for i in range(n)]
```
*Thanks to @xnor for golfing off 2 bytes!*
Try it on [Ideone](http://ideone.com/Gbqc29).
### How it works
If **i** is a number in **[0, ..., n - 1]**, then **~i % n = -(i + 1) % n = -(i + 1) + n = (n - 1) - i**, meaning that it maps **0** to **n - 1**, **1** to **n - 2** and, in general, the **j**th item from the left to the **j**th from the right.
As explained in [my Jelly answer](https://codegolf.stackexchange.com/a/71792), we can construct the output by peeking at the lower value among **i** and **~i % n**, and pick **i** if it is even and **~i % n** if it is odd. We achieve this as follows.
* If the minimum is even, `min(i,~i%n)%-2` will yield **0**, so XORing the result with **i** will yield **i**, and computing its residue modulo **n** will return **i**.
* If the minimum is odd, `min(i,~i%n)%-2` will yield **-1**, so XORing the result with **i** will yield **~i**, so the entire expression evaluates to **~i % n** as desired.
[Answer]
# PHP, ~~77~~ ~~76~~ ~~51~~ ~~50~~ 49 bytes
Uses ISO 8859-1 encoding.
Assembling the first half of the array like this:
* Odd numbers have their index value (1, 3, 5..)
* Even numbers have the value of `N+1-index` (9, 7, 5)
* This results in `1, 9, 3, 7, 5`
As for the second half of the array, the outermost values add up to `N+1`, which means you can get the corresponding right value from `N-[left value]` where the left value is already known.
```
for(;$k=$argv[1]-$j++;)echo" ",min($j,$k)%2?$j:$k;
```
Run like this (this also shows the total squared difference) (`-d` added for aesthetics only):
```
php -d error_reporting=32757 -r 'for(;$k=$argv[1]-$j++;)echo~ß,$x[]=min($j,$k)%2?$j:$k;  for(;$c=$x[+$i++];)$b+=($c-($x[$i]?:$x[0]))**2;echo"\n$b\n";' 10
```
* Saved a byte by negating left/right condition so the second ternary can be nested without parentheses
* Saved 25 bytes by shamelessly implementing Dennis' algorithm
* Saved a byte by getting rid of the needed space after `echo`
* Saved a byte by using `~ß` to yield a space.
[Answer]
# Python 2, 100
I know there's already a python answer, but I think I may have done this differently.
```
n=input();a=n%2;b=n/2;x=[b+1,b+a][a:]
for i in range(b+a-1):f=1-i%2*2;x=[x[-1]-f]+x+[x[0]+f]
print x
```
And as an extra to test the total score:
```
def t(x,n):return sum((x[i]-x[(i+1)%n])**2for i in range(n))
```
[Answer]
# CJam, ~~17~~ ~~15~~ 14 bytes
```
{,W%ee_::e<.=}
```
This is a function that pops an integer **n** from the stack and pushes a permutation of **[0 … n-1]** in return. The code uses the same approach as [my Jelly answer](https://codegolf.stackexchange.com/a/71792).
[Try it online!](http://cjam.tryitonline.net/#code=cX4gICAgICAgICAgICAgICBlIyBSZWFkIGFuZCBldmFsIGlucHV0Lgp7LFclZWVfOjplPC49fQp-cCAgICAgICAgICAgICAgIGUjIEV4ZWN1dGUgYW5kIHByaW50Lg&input=MTA)
### How it works
```
,W%ee_::e<.=    Function body. Stack: N
,               Turn N into [0 ... N-1].
 W%             Reverse to push [N-1 ... 0].
   ee           Enumerate. This pushes [[0 N-1] [1 N-2] ... [N-2 1] [N-1 0]].
     _          Push a copy of the array of pairs.
      ::e<      Reduce each pair by minimum.
          .=    Vectorized selection.
                For the Ith minimum M, select the Mth element of the Ith pair.
                Indices are modular and 0-based in CJam, so this selects the first
                element if the minimum is even, and the second one if it is odd.
```
[Answer]
## LISP, 86 bytes
```
(defun g(n m)(if(= n m)(list n)(if(< m n)(cons m(reverse(cons n(g(- n 1)(+ m 1))))))))
```
The inputs of the function allow to choose the start (m) and the end (n) values of the sequence. 
For testing the function according to the provided samples, n is fixed to N and m to 1. 
Here the code to test the function:
```
    (defun g(n m)(if(= n m)(list n)(if(< m n)(cons m(reverse(cons n(g(- n 1)(+ m 1))))))))
(defun sq (c)
    (apply #'+ (mapcar #'(lambda(x y) (* (- x y) (- x y))) c (append (cdr c) (list (car c))))))
(format t "N~20TSequence~50TSquared Difference~%")
(mapcar #'(lambda (x)(format t "~S~20T~S~50T~S~%" x (g x 1) (sq (g x 1)))) '(1 2 3 4 5 6 7 8 9 10 33 100 333 1000))
```
Try it on [Ideone](http://ideone.com/CuIn9b)!
[Answer]
# Julia, 39 bytes
```
n->map(i->min(i-1,n-i)%2>0?n-~-i:i,1:n)
```
This prints a permutation of **1:n**. A permutation of **0:n-1** does neither cost nor save bytes:
```
n->map(i->min(i,n+~i)%2>0?i:n+~i,0:n-1)
```
This last version is a direct port of [my Python answer](https://codegolf.stackexchange.com/a/72012).
[Answer]
## ES6, 77 bytes
```
n=>[...Array(n)].map(_=>r[++i&2?"push":"unshift"](i&1?n--:++j),i=j=0,r=[])&&r
```
The `i&1` samples the digits from the extremes to the middle. The `i&2` adds them to the beginning or end of the result in pairs.
[Answer]
# R, ~~117~~ 86 bytes
```
z=1:(n<-scan());a=pmin(z,n:1);for(i in seq(2,,2,n%/%2))z[b]=z[rev(b<-which(a==i,T))];z
```
*edit* replaced buggy long version with an implementation of @Dennis' Jelly algorithm
]