When `k = n-1`

, a valid construction is `[1, n, 2, n-1, 3, n-2, ....]`

. One way to see this is, we need to have a difference of `n-1`

, which means we need `1`

and `n`

adjacent; then, we need a difference of `n-2`

, etc.

This leads to the following idea: we will put `[1, 2, ...., n-k-1]`

first, and then we have `N = k+1`

adjacent numbers left, of which we want `k`

different differences. This is just the answer above translated by `n-k-1`

: we'll put `[n-k, n, n-k+1, n-1, ....]`

after.

```
def constructArray(self, n, k):
ans = range(1, n - k)
for d in xrange(k+1):
if d % 2 == 0:
ans.append(n-k + d/2)
else:
ans.append(n - d/2)
return ans
```