You have array a that contains all integers from 1 to n twice. You can arbitrary permute any numbers in a.

Let number i be in positions x_{i}, y_{i} (x_{i} < y_{i}) in the permuted array a. Let's define the value d_{i} = y_{i} - x_{i} — the distance between the positions of the number i. Permute the numbers in array a to minimize the value of the sum $s = \sum_{i = 1}^{n}(n - i) \cdot|d_{i} + i - n$.


-----Input-----

The only line contains integer n (1 ≤ n ≤ 5·10^5).


-----Output-----

Print 2n integers — the permuted array a that minimizes the value of the sum s.


-----Examples-----
Input
2

Output
1 1 2 2

Input
1

Output
1 1

Difficulty: interview

Starter code:

Solutions:
n=int(input())
A = [0] * (2*n)
per1 = 0
per2 = n
for i in range(1, n):
    if i % 2==1:
        A[per1] = i
        A[per1+n-i] = i
        per1+=1
    else:
        A[per2] = i
        A[per2+n-i] = i
        per2+=1

A[-1] = n
if n % 2 == 1:
    A[n//2] = n
else:
    A[-(n//2+1)] = n
print(' '.join(map(str, A)))

#!/usr/bin/env python3


def make_seq(n):
    os = list(range(1, n, 2))
    es = list(range(2, n, 2))
    ls = os[:]
    if n % 2 != 0:
        ls += [n]
    ls += os[::-1]
    ls += [n]
    ls += es
    if n % 2 == 0:
        ls += [n]
    ls += es[::-1]
    return ls


def main():
    print(' '.join(str(n) for n in make_seq(int(input()))))


def __starting_point():
    main()

__starting_point()

def __starting_point():

    n = int(input())
    res = [n]*(2*n)

    if n % 2 == 0:
        for i in range(1,n+1,2):
            index = i//2
            res[index] = i
            res[n-1-index] = i

        for i in range(2,n+1,2):
            index = i//2-1
            res[n+index] = i
            res[2*n-2-index] = i

    else:
        m = n//2*2
        for i in range(2,n+1,2):
            index = i//2-1
            res[index] = i
            res[m-1-index] = i
        #print(" ".join(map(str,res)))

        for i in range(1,n+1,2):
            index = i//2
            res[m+index] = i
            res[2*n-2-index] = i
        #print(" ".join(map(str,res)))

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

__starting_point()

import collections
import math

n  = int(input())
arr = [0] * (2 * n)
l, r = 0, 0
for i in range(1, n):
    if i % 2 == 1:
        arr[l] = arr[l + n - i] = i
        l += 1
    else:
        arr[n + r] = arr[n + r + n - i] = i
        r += 1
for i in range(2):
    while arr[l]:
        l += 1
    arr[l] = n
print(' '.join(str(x) for x in arr))

n = int(input())
A = [i for i in range(1, n+1, 2)]
B = [i for i in range(n-2 if n%2 else n-1, 0, -2)]
C = [i for i in range(2, n+1, 2)]
D = [i for i in range(n-1 if n%2 else n-2, 0, -2)]
ans = ' '.join(map(str, A+B+C+D+[n]))
print(ans)


N = int( input() )
ans = [ N for i in range( 2 * N ) ]
for i in range( 1, N + 1 ):
  x = i // 2 if i & 1 else N - 1 + i // 2
  y = x + N - i
  ans[ x ], ans[ y ] = i, i
print( *ans )


n = int(input())
r = list(range(n))
a, b = r[2 - n % 2::2], r[1 + n % 2::2]
print(' '.join(map(str, a + [n] + a[::-1] + b + b[::-1] + [n])))

n = int(input())

a = list(range(n % 2 + 1, n, 2))

a.extend(list(range(n - 1, 0, -2)))

a.append(n)

a.extend(list(range(2 - n % 2, n + 1, 2)))

a.extend(list(range(n - 2, 0, -2)))

print(*a)


#                                               |
#   _` |  __ \    _` |   __|   _ \   __ \    _` |   _` |
#  (   |  |   |  (   |  (     (   |  |   |  (   |  (   |
# \__,_| _|  _| \__,_| \___| \___/  _|  _| \__,_| \__,_|

import sys
import math

def read_line():
	return sys.stdin.readline()[:-1]
 
def read_int():
	return int(sys.stdin.readline())
	
def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

n = read_int()
x1 = 0
y1 = n
ans = [0]*(2*n)

for i in range(1,n+1):
	if i&1:
		ans[x1] = i
		ans[x1+n-i] = i
		x1+=1
	else:
		ans[y1] = i
		ans[y1+n-i] = i
		y1+=1

for i in range(2*n):
	if ans[i] == 0:
		ans[i] = n

print(*ans)



n=int(input())
if n%2==0:
    a=[]
    for i in range(1,n,2):
        a.append(i)
    a=a+a[::-1]
    b=[]
    for i in range(2,n,2):
        b.append(i)
    a=a+[n]+b+[n]+b[::-1]
    print(*a)
else:
    a=[]
    for i in range(1,n,2):
        a.append(i)
    a=a+[n]+a[::-1]+[n]
    b=[]
    for i in range(2,n,2):
        b.append(i)
    a=a+b+b[::-1]
    print(*a)

import sys
input=sys.stdin.readline
n=int(input())
if n%2==0:
    a=[]
    for i in range(1,n,2):
        a.append(i)
    a=a+a[::-1]
    b=[]
    for i in range(2,n,2):
        b.append(i)
    a=a+[n]+b+[n]+b[::-1]
    print(*a)
else:
    a=[]
    for i in range(1,n,2):
        a.append(i)
    a=a+[n]+a[::-1]+[n]
    b=[]
    for i in range(2,n,2):
        b.append(i)
    a=a+b+b[::-1]
    print(*a)