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: HARD
Tags: Constructive algorithms

Starter code:

Solutions:
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)


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)


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')
from itertools import permutations as perm

def calc(a):
	cost = 0
	index = dd(list)
	n = len(a)
	for i in range(n):
		index[a[i]].append(i)
	n //= 2
	for i in range(1, n + 1):
		d = index[i][1] - index[i][0]
		cost += (n - i) * abs(d + i - n)
	return cost

def solve():
	n = geta()
	diff = n - 1
	ans = [0] * (2 * n)
	index = 0
	for i in range(1, n, 2):
		ans[index] = i
		ans[index + diff] = i
		diff -= 2
		while index < 2 * n and ans[index]:
			index += 1
		if index == 2 * n:
			break
	index = n
	diff = n - 2
	for i in range(2, n, 2):
		ans[index] = i
		ans[index + diff] = i
		diff -= 2
		while index < 2 * n and ans[index]:
			index += 1
	for i in range(2 * n):
		if not ans[i]:
			ans[i] = n
	print(*ans)
solve()


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)


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())
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])))


from collections import defaultdict
import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = [-1] * (2 * n + 1)
if n % 2 == 0:
	i = 1
	pos = 1
	while i < n:
		a[pos] = i
		a[n - pos + 1] = i
		i += 2
		pos += 1
	i = 2
	pos = n + 1
	j = 1
	while i < n:
		a[pos] = i
		a[2 * n - j] = i
		j += 1
		pos += 1
		i += 2
	for i in range(1, len(a)):
		if a[i] == -1:
			a[i] = n
	print(*a[1:])
else:
	i = 2
	even = n - 1
	pos = 1
	while i < n:
		a[pos] = i
		a[even - pos + 1] = i
		i += 2
		pos += 1
	i = 1
	pos = n
	j = 1
	while i < n:
		a[pos] = i
		a[2 * n - j] = i
		i += 2
		pos += 1
		j += 1
	for i in range(1, len(a)):
		if a[i] == -1:
			a[i] = n
	print(*a[1:])


import sys
n = int(input())
a = [n] * (n * 2)

def solve(i, x):
	if x == 0:
		return i
	if n - x & 1:
		for num in range(1 if x & 1 else 2, x + 1, 2):
			a[i] = num
			i += 1
		for num in range(x, 0, -2):
			a[i] = num
			i += 1
	else:
		for num in range(1 if x & 1 else 2, x + 1, 2):
			a[i] = num
			i += 1
		i += 1
		for num in range(x, 0, -2):
			a[i] = num
			i += 1
	return i
i = solve(0, n - 1)
solve(i, n - 2)
sys.stdout.buffer.write(' '.join(map(str, a)).encode('utf-8'))


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
	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)))


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)


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)


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)))


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())))))
main()


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