Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Consider the following algorithm, which generates a (not necessarily uniformly) random permutation of numbers $1$ through $N$:

P := [1, 2, ..., N]
for i in 1..N do
j := rand(1, N)
swap(P[i], P[j])

Here, rand(1, N) returns a uniformly random integer between $1$ and $N$ inclusive. Let's denote the probability that the permutation generated by this algorithm is $P$ by $p(P)$.

Find a permutation $P_{1}$ such that $p(P_{1})$ is maximum possible and a permutation $P_{2}$ such that $p(P_{2})$ is minimum possible.

------  Input ------
The first and only line of the input contains a single integer $N$.

------  Output ------
Print two lines. The first line should contain $N$ space-separated integers denoting your permutation $P_{1}$. The second line should contain $N$ space-separated integers denoting your permutation $P_{2}$.

If there are multiple answers, you may print any one.

------  Constraints  ------
$1 ≤ N ≤ 17$

------  Subtasks ------
Subtask #1 (20 points): $1 ≤ N ≤ 7$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2
----- Sample Output 1 ------ 
1 2
2 1
----- explanation 1 ------ 
There are two possible permutations, $[1, 2]$ and $[2, 1]$. Both are equally likely to appear as the result of the given algorithm, so any pair of permutations is a valid answer.

Difficulty: MEDIUM_HARD
Tags: Probability

Constructive algorithms

String algorithms

Mathematics

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
l = []
for i in range(1, n + 1):
	l.append(i)
if n % 2 == 0:
	d = l[:n // 2]
	v = l[n // 2:]
	for j in range(1, len(d)):
		print(d[j], end=' ')
	print(d[0], end=' ')
	for k in range(1, len(v)):
		print(v[k], end=' ')
	print(v[0])
else:
	c = (n - 1) // 2
	d = l[:c]
	v = l[c:]
	for j in range(1, len(d)):
		print(d[j], end=' ')
	print(d[0], end=' ')
	for k in range(1, len(v)):
		print(v[k], end=' ')
	print(v[0])
print(n, end=' ')
for z in range(1, n):
	print(z, end=' ')
print()


n = int(input())
arr = []
for i in range(1, n + 1):
	arr.append(i)
if n % 2 == 0:
	d = arr[:n // 2]
	v = arr[n // 2:]
	for i in range(1, len(d)):
		print(d[i], end=' ')
	print(d[0], end=' ')
	for i in range(1, len(v)):
		print(v[i], end=' ')
	print(v[0])
else:
	c = (n - 1) // 2
	d = arr[:c]
	v = arr[c:]
	for i in range(1, len(d)):
		print(d[i], end=' ')
	print(d[0], end=' ')
	for i in range(1, len(v)):
		print(v[i], end=' ')
	print(v[0])
print(n, end=' ')
for i in range(1, n):
	print(i, end=' ')
print('  ')


n = int(input())
if n == 1:
	print('1')
	print('1')
if n == 2:
	print('1 2')
	print('2 1')
if n == 3:
	print('1 3 2')
	print('3 1 2')
if n == 4:
	print('2 1 4 3')
	print('4 1 2 3')
if n == 5:
	print('2 1 4 5 3')
	print('5 1 2 3 4')
if n == 6:
	print('2 3 1 5 6 4')
	print('6 1 2 3 4 5')
if n == 7:
	print('2 3 1 5 6 7 4')
	print('7 1 2 3 4 5 6')
if n == 8:
	print('2 3 4 1 6 7 8 5')
	print('8 1 2 3 4 5 6 7')
if n == 9:
	print('2 3 4 1 6 7 8 9 5')
	print('9 1 2 3 4 5 6 7 8')
if n == 10:
	print('2 3 4 5 1 7 8 9 10 6')
	print('10 1 2 3 4 5 6 7 8 9')
if n == 11:
	print('2 3 4 5 1 7 8 9 10 11 6')
	print('11 1 2 3 4 5 6 7 8 9 10')
if n == 12:
	print('2 3 4 5 6 1 8 9 10 11 12 7')
	print('12 1 2 3 4 5 6 7 8 9 10 11')
if n == 13:
	print('2 3 4 5 6 1 8 9 10 11 12 13 7')
	print('13 1 2 3 4 5 6 7 8 9 10 11 12')
if n == 14:
	print('2 3 4 5 6 7 1 9 10 11 12 13 14 8')
	print('14 1 2 3 4 5 6 7 8 9 10 11 12 13')
if n == 15:
	print('2 3 4 5 6 7 1 9 10 11 12 13 14 15 8')
	print('15 1 2 3 4 5 6 7 8 9 10 11 12 13 14')
if n == 16:
	print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 9')
	print('16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15')
if n == 17:
	print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 17 9')
	print('17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16')


n = int(input())
b = [I for I in range(1, n + 1)]
r1 = b[-1:] + b[0:-1]
c = n // 2 + n % 2
l1 = b[:c]
l2 = b[c:]
r2 = l1[1:] + l1[0:1] + l2[1:] + l2[0:1]
for i in range(len(r2)):
	print(r2[i], end=' ')
for i in range(len(r1)):
	print(r1[i], end=' ')


N = int(input())
B = [I for I in range(1, N + 1)]
r1 = B[-1:] + B[0:-1]
c = N // 2 + N % 2
l1 = B[:c]
l2 = B[c:]
r2 = l1[1:] + l1[0:1] + l2[1:] + l2[0:1]
for i in range(len(r2)):
	print(r2[i], end=' ')
print()
for i in range(len(r1)):
	print(r1[i], end=' ')


def rotate(l):
	return l[1:] + l[:1]
n = int(input())
p2 = [n] + list(range(1, n))
c = n // 2
p1 = list(range(1, n + 1))
ans = rotate(p1[:c]) + rotate(p1[c:])
print(*ans)
print(*p2)


n = int(input())
a = []
if n == 1:
	a.append(1)
elif n % 2 == 0:
	for i in range(2, n // 2 + 1):
		a.append(i)
	a.append(1)
	for i in range(n // 2 + 2, n + 1):
		a.append(i)
	a.append(n // 2 + 1)
else:
	for i in range(2, n // 2 + 2):
		a.append(i)
	a.append(1)
	for i in range(n // 2 + 3, n + 1):
		a.append(i)
	a.append(n // 2 + 2)
print(' '.join(map(str, a)))
b = [n] + list(range(1, n))
print(' '.join(map(str, b)))


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import *

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
N = read()
minp = [N] + list(range(1, N))
h = N // 2
p = list(range(1, N + 1))

def rotate(xs):
	return xs[1:] + xs[:1]
maxp = rotate(p[:h]) + rotate(p[h:])
print(' '.join(map(str, maxp)))
print(' '.join(map(str, minp)))


n = int(input())
t = n // 2
arr = [0] * n
if n == 1:
	for i in range(2):
		print(n)
elif n == 2:
	print('1 2')
	print('2 1')
else:
	arr[t - 1] = 1
	if t - 1 != 0:
		arr[0] = 2
	e = 3
	for m in range(1, t - 1):
		arr[m] = e
		e += 1
	arr[t] = t + 2
	arr[-1] = t + 1
	e = t + 3
	for m in range(t + 1, n - 1):
		arr[m] = e
		e += 1
	for item in arr:
		print(item, end=' ')
	print()
	arr[0] = n
	for j in range(1, n):
		arr[j] = j
	for item in arr:
		print(item, end=' ')


n = int(input())
p = [x for x in range(1, n + 1)]
q = [x for x in range(n + 1)]
p.append(1)
if n % 2 == 0:
	(p[n // 2], p[n]) = (p[n], p[n // 2])
else:
	(p[n // 2 + 1], p[n]) = (p[n], p[n // 2 + 1])
print(*p[1:])
q = q[n:] + q[1:n]
print(*q)


n = int(input())

def shuffle(ordre):
	ls = [i + 1 for i in range(len(ordre))]
	for i in range(len(ordre)):
		swap(ls, i, ordre[i])
	return ls

def swap(ls, i, j):
	(ls[i], ls[j]) = (ls[j], ls[i])
	return ls

def f_maxi(n):
	if n != 1:
		l = [i + 1 for i in range(n)]
		l1 = l[0:n // 2]
		deb = l1[0]
		for i in range(len(l1) - 1):
			l1[i] = l1[i + 1]
		l1[-1] = deb
		l2 = l[n // 2:n]
		deb = l2[0]
		for i in range(len(l2) - 1):
			l2[i] = l2[i + 1]
		l2[-1] = deb
		return l1 + l2
	else:
		return [1]
mini = shuffle([n - 1 for i in range(n)])
l = [0 for i in range(n)]
l[n - 1] = 1
maxi = f_maxi(n)
print(' '.join([str(i) for i in maxi]))
print(' '.join([str(i) for i in mini]))


n = int(input())
arr = [i for i in range(0, n + 1)]
for i in range(1, n):
	if i != n // 2:
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
for i in range(1, n + 1):
	print(arr[i], end=' ')
print()
print(n, end=' ')
for i in range(1, n):
	print(i, end=' ')


n = int(input())
if n == 2:
	print(1, 2)
	print(1, 2)
elif n == 3:
	print(1, 3, 2)
	print(3, 2, 1)
elif n == 4:
	print(2, 1, 4, 3)
	print(4, 2, 3, 1)
elif n == 5:
	print(2, 1, 4, 5, 3)
	print(5, 1, 2, 3, 4)
elif n == 7:
	print(2, 3, 1, 5, 6, 7, 4)
	print(7, 1, 2, 3, 4, 5, 6)
elif n == 10:
	print('va')
elif n == 9:
	print(2, 3, 4, 1, 6, 7, 8, 9, 5)
	print(n, *range(2, n))
else:
	A = list(range(1, n // 2)) + [0] + list(range(n // 2 + 1, n)) + [n // 2]
	print(*[a + 1 for a in A])
	print(n, *range(1, n))


n = int(input())
if n == 2:
	print(1, 2)
	print(1, 2)
elif n == 3:
	print(1, 3, 2)
	print(3, 2, 1)
elif n == 4:
	print(2, 1, 4, 3)
	print(4, 2, 3, 1)
elif n == 5:
	print(2, 1, 4, 5, 3)
	print(5, 1, 2, 3, 4)
elif n == 7:
	print(2, 3, 1, 5, 6, 7, 4)
	print(7, 1, 2, 3, 4, 5, 6)
else:
	A = list(range(1, n // 2)) + [0] + list(range(n // 2 + 1, n)) + [n // 2]
	print(*[a + 1 for a in A])
	print(n, *range(1, n))


n = int(input())
for i in range(1, n + 1):
	if i < n // 2:
		print(i + 1, end=' ')
	elif i == n // 2:
		print(1, end=' ')
	elif i == n:
		print(n // 2 + 1)
	else:
		print(i + 1, end=' ')
print(n, end=' ')
for i in range(1, n - 1):
	print(i, end=' ')
print(n - 1)


n = int(input())
print(*range(2, n // 2 + 1 + n % 2), 1, *range(n // 2 + 2 + n % 2, n + 1), n // 2 + 1 + n % 2, '\r' + str(n), *range(1, n))


n = int(input())
if n > 1:
	minli = [n] + [i for i in range(1, n)]
	maxli = [i for i in range(1, n + 1)]
	for i in range(0, n // 2 - 1):
		(maxli[i], maxli[i + 1]) = (maxli[i + 1], maxli[i])
	for i in range(n // 2, n - 1):
		(maxli[i], maxli[i + 1]) = (maxli[i + 1], maxli[i])
	for i in maxli:
		print(i, end=' ')
	print()
	for i in minli:
		print(i, end=' ')
else:
	minli = [1]
	maxli = [1]
	print(1)
	print(1)


from math import ceil
N = int(input())
maxP = [N] + [i for i in range(1, N)]
if N > 2:
	minP = [i for i in range(2, ceil(N / 2) + 1)]
	minP.append(1)
	minP = minP + [i for i in range(ceil(N / 2) + 1 + 1, N + 1)]
	minP.append(ceil(N / 2) + 1)
	for a in minP:
		print(a, end=' ')
	print()
	for a in maxP:
		print(a, end=' ')
elif N == 1:
	print(1)
	print(1)
elif N == 2:
	print('2 1')
	print('1 2')


N = int(input())
for i in range(2, N // 2 + 1):
	print(i, end=' ')
if N is not 1:
	print(1, end=' ')
for i in range(N // 2 + 2, N + 1):
	print(i, end=' ')
print(N // 2 + 1)
print(N, end=' ')
for i in range(1, N):
	print(i, end=' ')
print()


n = int(input())
l = ['1', '1 2', '2 1 3', '2 1 4 3', '2 3 1 5 4', '2 3 1 5 6 4', '2 3 4 1 6 7 5', '2 3 4 1 6 7 8 5', '2 3 4 5 1 7 8 9 6', '2 3 4 5 1 7 8 9 10 6', '2 3 4 5 6 1 8 9 10 11 7', '2 3 4 5 6 1 8 9 10 11 12 7', '2 3 4 5 6 7 1 9 10 11 12 13 8', '2 3 4 5 6 7 1 9 10 11 12 13 14 8', '2 3 4 5 6 7 8 1 10 11 12 13 14 15 9', '2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 9', '2 3 4 5 6 7 8 9 1 11 12 13 14 15 16 17 10']
print(l[n - 1])
s = ''
for i in range(n - 1):
	s = s + str(i + 1) + ' '
print(str(n) + ' ' + s)


import math

def f(arr):
	m = math.ceil(len(arr) / 2) - 1
	mn = []
	mx = []
	mn.append(arr[len(arr) - 1])
	for i in range(len(arr) - 1):
		mn.append(arr[i])
	for i in range(1, m + 1):
		mx.append(arr[i])
	mx.append(arr[0])
	for i in range(m + 2, len(arr)):
		mx.append(arr[i])
	mx.append(arr[m + 1])
	return (mx, mn)
n = int(input())
arr = [i for i in range(1, n + 1)]
(mx, mn) = f(arr)
for i in mx:
	print(i, end=' ')
print()
for i in mn:
	print(i, end=' ')
print()


n = int(input())
if n == 1:
	print(1)
	print(1)
	exit()
elif n == 3:
	print(2, 3, 1)
	print(3, 1, 2)
	exit()
for i in range(2, n // 2 + 1):
	print(i, end=' ')
print(1, end=' ')
for i in range(n // 2 + 2, n + 1):
	print(i, end=' ')
print(n // 2 + 1)
print(n, end=' ')
for i in range(1, n):
	print(i, end=' ')


n = int(input())
if n == 1:
	print('1')
	print('1')
elif n == 2:
	print('1 2')
	print('2 1')
elif n == 3:
	print('2 1 3')
	print('3 1 2')
else:
	med = n // 2
	print(' '.join([str(x) for x in range(2, med + 1)]), 1, ' '.join([str(x) for x in range(med + 2, n + 1)]), med + 1)
	print(n, end=' ')
	for i in range(1, n):
		print(i, end=' ')


n = int(input())
max = [1, 12, 231, 2143, 21453, 214563, 2315674, 23416785, 234167895]
min = [1, 21, 123, 4123, 51234, 612345, 7123456, 81234567, 912345678]
if n < 10:
	opmin = ' '.join(list(str(min[n - 1])))
	opmax = ' '.join(list(str(max[n - 1])))
	print(opmax)
	print(opmin)
elif n == 10:
	print('2 3 4 5 1 7 8 9 10 6')
	print('10 1 2 3 4 5 6 7 8 9')
elif n == 11:
	print('2 3 4 5 1 7 8 9 10 11 6')
	print('11 1 2 3 4 5 6 7 8 9 10')
elif n == 12:
	print('2 3 4 5 6 1 8 9 10 11 12 7')
	print('12 1 2 3 4 5 6 7 8 9 10 11')
elif n == 13:
	print('2 3 4 5 6 1 8 9 10 11 12 13 7')
	print('13 1 2 3 4 5 6 7 8 9 10 11 12')
elif n == 14:
	print('2 3 4 5 6 7 1 9 10 11 12 13 14 8')
	print('14 1 2 3 4 5 6 7 8 9 10 11 12 13')
elif n == 15:
	print('2 3 4 5 6 7 1 9 10 11 12 13 14 15 8')
	print('15 1 2 3 4 5 6 7 8 9 10 11 12 13 14')
elif n == 16:
	print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 9')
	print('16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15')
elif n == 17:
	print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 17 9')
	print('17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16')


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


n = int(input())
if n == 1:
	print(1)
	print(1)
else:
	k = []
	for i in range(2, n // 2 + 1):
		k.append(i)
	k.append(1)
	for i in range(n // 2 + 2, n + 1):
		k.append(i)
	k.append(n // 2 + 1)
	k1 = []
	k1.append(n)
	for i in range(1, n):
		k1.append(i)
	print(*k)
	print(*k1)


n = int(input())
temp = []
for i in range(n):
	temp.append(i + 1)
if n == 1:
	print(temp[0])
	print(temp[0])
if n > 1 and n % 2 == 0:
	max_ans = []
	if n <= 4:
		for i in range(len(temp)):
			if i % 2 == 0:
				max_ans.append(temp[i] + 1)
			else:
				max_ans.append(temp[i] - 1)
	else:
		for i in range(len(temp)):
			if i < len(temp) // 2 - 1 or (i >= len(temp) // 2 and i < len(temp) - 1):
				max_ans.append(temp[i] + 1)
			elif i == len(temp) // 2 - 1:
				max_ans.append(temp[i] - len(temp) // 2 + 1)
			else:
				max_ans.append(temp[i] - (n - n // 2 - 1))
	min_ans = []
	min_ans.append(temp[n - 1])
	for i in range(len(temp) - 1):
		min_ans.append(temp[i])
elif n > 1 and n % 2 == 1:
	max_ans = []
	for i in range(len(temp)):
		if i < len(temp) // 2 or (i > len(temp) // 2 and i < len(temp) - 1):
			max_ans.append(temp[i] + 1)
		elif i == len(temp) // 2:
			max_ans.append(temp[i] - len(temp) // 2)
		else:
			max_ans.append(temp[i] - (n - n // 2 - 2))
	min_ans = []
	min_ans.append(temp[n - 1])
	for i in range(n - 1):
		min_ans.append(temp[i])
for i in max_ans:
	print(i, end=' ')
print()
for i in min_ans:
	print(i, end=' ')


import math
n = int(input())
a = list(range(1, math.ceil(n / 2) + 1))
b = list(range(math.ceil(n / 2) + 1, n + 1))
a.append(a.pop(0))
b.append(b.pop(0))
print(*a, *b)
c = list(range(1, n + 1))
c.insert(0, c.pop(-1))
print(*c)


n = int(input())
middle = n / 2
if middle * 10 % 10 != 0:
	middle = int(middle) + 1
middle = int(middle)
for i in range(1, middle):
	print(i + 1, end=' ')
print(1, end=' ')
for i in range(middle + 2, n + 1):
	print(i, end=' ')
print(middle + 1, end='\n')
print(n, end=' ')
for i in range(n - 1):
	print(i + 1, end=' ')


import sys
import math
fileoperation = 0
if fileoperation:
	orig_stdout = sys.stdout
	orig_stdin = sys.stdin
	inputfile = open('W:/Competitive Programming/input.txt', 'r')
	outputfile = open('W:/Competitive Programming/output.txt', 'w')
	sys.stdin = inputfile
	sys.stdout = outputfile
mod = 1000000007

def nospace(l):
	ans = ''.join((str(i) for i in l))
	return ans

def eve(n):
	ans = []
	v = n // 2
	for i in range(2, v + 1):
		ans.append(i)
	ans.append(1)
	for i in range(v):
		ans.append(ans[i] + v)
	return ans
t = 1
for tt in range(t):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
		continue
	elif n % 2 == 0:
		print(*eve(n))
	else:
		ans = eve(n + 1)
		new = []
		for i in range(n + 1):
			if ans[i] != n + 1:
				new.append(ans[i])
		print(*new)
	minn = []
	minn.append(n)
	for i in range(1, n):
		minn.append(i)
	print(*minn)
if fileoperation:
	sys.stdout = orig_stdout
	sys.stdin = orig_stdin
	inputfile.close()
	outputfile.close()


t = int(input())
if t == 2:
	print('1 2')
if t == 3:
	print('1 3 2')
if t == 4:
	print('2 1 4 3')
if t == 5:
	print('2 3 1 5 4')
if t == 6:
	print('2 3 4 1 6 5')
if t == 7:
	print('2 3 4 1 6 7 5')
if t == 8:
	print('2 3 4 5 1 7 8 6')
if t == 9:
	print('2 3 4 5 1 7 8 9 6')
if t == 10:
	print('2 3 4 5 6 1 8 9 10 7')
if t == 11:
	print('2 3 4 5 6 1 8 9 10 11 7')
if t == 12:
	print('2 3 4 5 6 1 8 9 10 11 12 7')
if t == 13:
	print('2 3 4 5 6 7 1 9 10 11 12 13 8')
if t == 14:
	print('2 3 4 5 6 7 1 9 10 11 12 13 14 8')
if t == 15:
	print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 9')
if t == 16:
	print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 9')
if t == 17:
	print('2 3 4 5 6 7 8 9 1 11 12 13 14 15 16 17 10')
print(t, end=' ')
for i in range(1, t):
	print(i, end=' ')


n = int(input())
arr = []
for i in range(1, n + 1):
	arr.append(i)
arr2 = arr.copy()
if n % 2 != 0:
	i = 0
	while i < n // 2:
		temp = arr2[i]
		arr2[i] = arr2[i + 1]
		arr2[i + 1] = temp
		i += 1
	i = n // 2 + 1
	while i < n - 1:
		temp = arr2[i]
		arr2[i] = arr2[i + 1]
		arr2[i + 1] = temp
		i += 1
	for i in range(n):
		print(arr2[i], end=' ')
else:
	i = 0
	while i < n // 2 - 1:
		temp = arr2[i]
		arr2[i] = arr2[i + 1]
		arr2[i + 1] = temp
		i += 1
	i = n // 2
	while i < n - 1:
		temp = arr2[i]
		arr2[i] = arr2[i + 1]
		arr2[i + 1] = temp
		i += 1
	for i in range(n):
		print(arr2[i], end=' ')
print('\r')
arr = arr[-1:] + arr[:-1]
for i in range(n):
	print(arr[i], end=' ')
print('\r')


n = int(input())
a = [i for i in range(1, n + 1)]
if n == 2:
	print(1, 2)
	print(2, 1)
elif n == 3:
	print(1, 3, 2)
	print(1, 2, 3)
else:
	min_a = []
	min_a.append(n)
	for i in range(1, n):
		min_a.append(i)
	max_a = []
	mid = (1 + n) // 2
	for i in range(2, mid + 1):
		max_a.append(i)
	max_a.append(1)
	for i in range(mid + 2, n + 1):
		max_a.append(i)
	if n > 2:
		max_a.append(mid + 1)
	print(*max_a)
	print(*min_a)


n = int(input())
if n == 1:
	print(1)
	print(1)
	exit()
A = []
i = 2
j = 0
if n % 2 == 0:
	a = n // 2 - 1
else:
	a = n // 2
while j < a:
	A.append(i)
	i += 1
	j += 1
A.append(1)
a = i
i += 1
while i <= n:
	A.append(i)
	i += 1
A.append(a)
for i in A:
	print(i, end=' ')
print()
print(n, end=' ')
for i in range(1, n):
	print(i, end=' ')


n = int(input())
a = [i + 1 for i in range(n)]
if n == 3:
	a = [1, 3, 2]
elif n == 4:
	a = [2, 1, 4, 3]
if n > 4:
	if n < 7:
		a = [2, 3, 1]
		for i in range(5, n + 1):
			a.append(i)
		a.append(4)
	elif n < 9:
		a = [2, 3, 4, 1]
		for i in range(6, n + 1):
			a.append(i)
		a.append(5)
	elif n < 11:
		a = [2, 3, 4, 5, 1]
		for i in range(7, n + 1):
			a.append(i)
		a.append(6)
	elif n < 13:
		a = [2, 3, 4, 5, 6, 1]
		for i in range(8, n + 1):
			a.append(i)
		a.append(7)
	elif n < 15:
		a = [2, 3, 4, 5, 6, 7, 1]
		for i in range(9, n + 1):
			a.append(i)
		a.append(8)
	else:
		a = [2, 3, 4, 5, 6, 7, 8, 1]
		for i in range(10, n + 1):
			a.append(i)
		a.append(9)
if n == 2:
	print('2 1')
	print('2 1')
elif n == 1:
	print(1)
	print(1)
else:
	print(*a)
	b = [i + 1 for i in range(n - 1)]
	b.insert(0, n)
	print(*b)


N = int(input())
mn = [N]
for i in range(1, N):
	mn.append(i)
mx = [1]
for i in range(2, N + 1):
	mx.append(i)
mid = int(N / 2)
(mx[0], mx[mid]) = (mx[mid], mx[0])
for i in range(N - 1):
	if i != mid or i + 1 != mid:
		(mx[i], mx[i + 1]) = (mx[i + 1], mx[i])
MX = ''
MN = ''
for i in range(N):
	MX = MX + ' ' + str(mx[i])
	MN = MN + ' ' + str(mn[i])
print(MX)
print(MN)


import math
n = int(input())
start = []
for i in range(1, n + 1):
	start.append(str(i))
div = math.ceil(n / 2)
start1 = start[0:div]
start2 = start[div:n]
for i in range(div - 1):
	temp = start1[i]
	start1[i] = start1[i + 1]
	start1[i + 1] = temp
for i in range(n - div - 1):
	temp = start2[i]
	start2[i] = start2[i + 1]
	start2[i + 1] = temp
maximum = start1 + start2
minimum = [str(n)] + start[0:n - 1]
print(' '.join(maximum))
print(' '.join(minimum))


n = int(input())
s = []
if n == 3:
	s = [2, 1, 3]
elif n == 1:
	s = [1]
else:
	for i in range(2, int(n / 2) + 1):
		s.append(i)
	s.append(1)
	for i in range(int(n / 2) + 2, n + 1):
		s.append(i)
	s.append(int(n / 2) + 1)
print(' '.join((str(i) for i in s)))
s = []
s.append(n)
for i in range(1, n):
	s.append(i)
print(' '.join((str(i) for i in s)))


def get_all_substrings(string):
	length = len(string)
	for i in xrange(length):
		for j in xrange(i + 1, length + 1):
			yield string[i:j]

def eulers_gcd(russia, argentina):
	if russia == 0:
		return argentina
	return eulers_gcd(argentina % russia, russia)

def pretty(pre, n):
	for i in range(pre, n + 1):
		if i < n:
			print(i, end=' ')
		else:
			print(i, pre - 1)

def permutation(n):
	if n == 1:
		print(1)
		print(1)
	elif n == 2:
		print(1, 2)
		print(2, 1)
	elif n == 3:
		print(1, 3, 2)
		print(3, 2, 1)
	elif n == 4:
		print(2, 1, 4, 3)
		print(4, 2, 3, 1)
	elif n == 5:
		print(2, 1, 4, 5, 3)
		print(5, 1, 2, 3, 4)
	elif n == 6:
		print(2, 3, 1, 5, 6, 4)
		print(6, 1, 2, 3, 4, 5)
	elif n == 7:
		print(2, 3, 1, 5, 6, 7, 4)
		print(7, 1, 2, 3, 4, 5, 6)
	elif n > 7:
		res = n // 2
		c = 2
		defi = res + 1
		for i in range(c, defi + 1):
			if i != defi:
				print(i, end=' ')
			else:
				print(1, end=' ')
				pretty(defi + 1, n)
		for i in range(1, n + 1):
			if i == 1:
				print(n, end=' ')
			else:
				print(i - 1, end=' ')

def signum(first_number, second_number, modulo_operator):
	dracula = 1
	first_number = first_number % modulo_operator
	while second_number > 0:
		if second_number & 1 == 1:
			dracula = dracula * first_number % modulo_operator
		second_number = second_number // 2
		first_number = first_number * first_number % modulo_operator
	return dracula

def combine(a, b, mod__c):
	moddy = 1000000007
	a = a + b
	a = a % mod__c
	return a
n = int(input())
permutation(n)


a = int(input())
c = []
f = 1
for y in range(a):
	c.append(f)
	f += 1
if a == 1:
	print(1)
	print(1)
else:
	b = a % 2
	if b != 0:
		f = (a + 1) // 2
	else:
		f = a // 2
	for x in range(1, f):
		print(c[x], end=' ')
	print(c[0], end=' ')
	for x in range(f + 1, a):
		print(c[x], end=' ')
	print(c[f])
	print(c[a - 1], end=' ')
	for x in range(1, a):
		print(x, end=' ')


n = int(input())
print1 = []
print2 = [n]
add = n // 2
for i in range(2, n + 1):
	print1.append(i)
print1.append(1)
mid = n // 2
if n % 2 == 0:
	mid = mid - 1
(print1[mid], print1[n - 1]) = (print1[n - 1], print1[mid])
for i in range(1, n):
	print2.append(i)
print(*print1)
print(*print2)


def printmin(n):
	print(n, end=' ')
	for i in range(1, n):
		print(i, end=' ')
n = int(input())
if n == 1:
	print('1')
elif n == 2:
	print('1 2')
elif n == 3:
	print('1 3 2')
elif n == 4:
	print('2 1 4 3')
else:
	for i in range(2, n // 2 + 1):
		print(i, end=' ')
	print('1', end=' ')
	print(n // 2 + 2, end=' ')
	for i in range(n // 2 + 3, n + 1):
		print(i, end=' ')
	print(n // 2 + 1)
printmin(n)


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


n = int(input())
if n == 1:
	print(1)
	print(1)
elif n % 2 == 0:
	print(' '.join([str(x) for x in list(range(2, n // 2 + 1)) + [1] + list(range(n // 2 + 2, n + 1)) + list([n // 2 + 1])]).strip())
	print(' '.join([str(n)] + [str(x) for x in range(1, n)]))
else:
	print(' '.join([str(x) for x in list(range(2, n // 2 + 2)) + [1] + list(range(n // 2 + 3, n + 1)) + list([n // 2 + 2])]).strip())
	print(' '.join([str(n)] + [str(x) for x in range(1, n)]))


n = int(input())
p = [i for i in range(1, n + 1)]
p1 = p[1:n // 2] + [p[0]] + p[n // 2 + 1:] + [p[n // 2]]
p2 = [p[-1]] + p[:n - 1]
for i in p1:
	print(i, end=' ')
print()
for i in p2:
	print(i, end=' ')


n = int(input())
if n == 1:
	print('1\n1')
elif n == 2:
	print('1 2\n2 1')
elif n == 3:
	print('1 3 2\n1 2 3')
elif n == 4:
	print('2 1 4 3\n4 1 2 3')
elif n == 5:
	print('2 1 4 5 3\n5 1 2 3 4')
elif n == 6:
	print('2 3 1 5 6 4\n6 1 2 3 4 5')
elif n == 7:
	print('2 3 1 5 6 7 4\n7 1 2 3 4 5 6')
elif n == 8:
	print('2 3 4 1 6 7 8 5\n8 1 2 3 4 5 6 7')
elif n == 9:
	print('2 3 4 1 6 7 8 9 5\n9 1 2 3 4 5 6 7 8')
elif n == 10:
	print('2 3 4 5 1 7 8 9 10 6\n10 1 2 3 4 5 6 7 8 9')
elif n == 11:
	print('2 3 4 5 1 7 8 9 10 11 6\n11 1 2 3 4 5 6 7 8 9 10')
elif n == 12:
	print('2 3 4 5 6 1 8 9 10 11 12 7\n12 1 2 3 4 5 6 7 8 9 10 11')
elif n == 13:
	print('2 3 4 5 6 1 8 9 10 11 12 13 7\n13 1 2 3 4 5 6 7 8 9 10 11 12')
elif n == 14:
	print('2 3 4 5 6 7 1 9 10 11 12 13 14 8\n14 1 2 3 4 5 6 7 8 9 10 11 12 13')
elif n == 15:
	print('2 3 4 5 6 7 1 9 10 11 12 13 14 15 8\n15 1 2 3 4 5 6 7 8 9 10 11 12 13 14')
elif n == 16:
	print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 9\n16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15')
else:
	print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 17 9\n17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16')


def swap(arr, a, b):
	(arr[a], arr[b]) = (arr[b], arr[a])
n = int(input())
arr = [x for x in range(1, n + 1)]
if n % 2 == 0:
	p1 = n // 2 - 1
else:
	p1 = n // 2
p2 = p1 + 1
for i in range(p1):
	swap(arr, i, i + 1)
for i in range(p2, n - 1):
	swap(arr, i, i + 1)
for j in arr:
	print(j, '', end='')
print()
print(n, end=' ')
for i in range(1, n):
	print(i, end=' ')


n = int(input())
m = n // 2
buffer = []
for i in range(1, m):
	buffer.append(str(i + 1))
buffer.append(str(1))
for i in range(m + 1, n):
	buffer.append(str(i + 1))
buffer.append(str(m + 1))
print(' '.join(buffer))
buffer = []
buffer.append(str(n))
for i in range(0, n - 1):
	buffer.append(str(i + 1))
print(' '.join(buffer))


n = int(input())
p = []
q = []
if n == 1:
	p = [1]
	q = [1]
elif n == 2:
	p = [1, 2]
	q = [2, 1]
elif n == 3:
	p = [1, 3, 2]
	q = [3, 2, 1]
elif n == 4:
	p = [2, 1, 4, 3]
	q = [4, 1, 2, 3]
elif n == 5:
	p = [2, 3, 1, 5, 4]
	q = [5, 1, 2, 3, 4]
elif n == 6:
	p = [2, 3, 1, 5, 6, 4]
	q = [6, 1, 2, 3, 4, 5]
elif n == 7:
	p = [2, 3, 4, 1, 6, 7, 5]
	q = [7, 1, 2, 3, 4, 5, 6]
elif n == 8:
	p = [2, 3, 4, 1, 6, 7, 8, 5]
	q = [8, 1, 2, 3, 4, 5, 6, 7]
elif n == 9:
	p = [2, 3, 4, 5, 1, 7, 8, 9, 6]
	q = [9, 1, 2, 3, 4, 5, 6, 7, 8]
elif n == 10:
	p = [2, 3, 4, 5, 1, 7, 8, 9, 10, 6]
	q = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
elif n == 11:
	p = [2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 7]
	q = [11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
elif n == 12:
	p = [2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 12, 7]
	q = [12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
elif n == 13:
	p = [2, 3, 4, 5, 6, 7, 1, 9, 10, 11, 12, 13, 8]
	q = [13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
elif n == 14:
	p = [2, 3, 4, 5, 6, 7, 1, 9, 10, 11, 12, 13, 14, 8]
	q = [14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
elif n == 15:
	p = [2, 3, 4, 5, 6, 7, 8, 1, 10, 11, 12, 13, 14, 15, 9]
	q = [15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
elif n == 16:
	p = [2, 3, 4, 5, 6, 7, 8, 1, 10, 11, 12, 13, 14, 15, 16, 9]
	q = [16, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
elif n == 17:
	p = [2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 10]
	q = [17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
for i in range(len(p)):
	print(p[i], end=' ')
print('')
for i in range(len(q)):
	print(q[i], end=' ')


n = int(input())
m = n // 2
for i in range(2, m + 1):
	print(i, end=' ')
print(1, end=' ')
for i in range(m + 2, n + 1):
	print(i, end=' ')
print(m + 1)
print(n, end=' ')
for i in range(1, n):
	print(i, end=' ')


n = int(input())
a = []
for i in range(n):
	a.append(i + 1)
for i in range(int(n / 2)):
	(a[i + 1], a[i]) = (a[i], a[i + 1])
for j in range(i, n - 1):
	(a[j], a[j + 1]) = (a[j + 1], a[j])
for i in range(n):
	print(a[i], end=' ')
print()
print(n, end=' ')
for i in range(1, n):
	print(i, end=' ')


n = int(input())
if n == 1:
	print(n)
	print(n)
elif n == 2:
	print('1 2')
	print('2 1')
else:
	b = [n]
	for i in range(n):
		if i > 0:
			b.append(i)
	if n == 3:
		print('1 3 2')
	elif n == 4:
		print('2 1 4 3')
	elif n == 5:
		print('2 1 4 5 3')
	elif n == 6:
		print('2 3 1 5 6 4')
	elif n == 7:
		print('2 3 1 5 6 7 4')
	elif n == 8:
		print('2 3 4 1 6 7 8 5')
	elif n == 9:
		print('2 3 4 1 6 7 8 9 5')
	elif n == 10:
		print('2 3 4 5 1 7 8 9 10 6')
	elif n == 11:
		print('2 3 4 5 1 7 8 9 10 11 6')
	elif n == 12:
		print('2 3 4 5 6 1 8 9 10 11 12 7')
	elif n == 13:
		print('2 3 4 5 6 1 8 9 10 11 12 13 7')
	elif n == 14:
		print('2 3 4 5 6 7 1 9 10 11 12 13 14 8')
	elif n == 15:
		print('2 3 4 5 6 7 1 9 10 11 12 13 14 15 8')
	elif n == 16:
		print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 9')
	elif n == 17:
		print('2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 17 9')
	b = ' '.join((str(x) for x in b))
	print(b)


from math import floor

def makear(n):
	a = []
	for i in range(1, n + 1):
		a.append(i)
	return a

def maxlist(n):
	if n == 1:
		return [1]
	if n == 2:
		return [2, 1]
	if n == 3:
		return [2, 1, 3]
	if n % 2 == 1:
		max = maxlist(n - 1)[:]
		k = len(max)
		max.append(n)
		(max[k], max[k - 1]) = (max[k - 1], max[k])
		return max
	f = floor(n / 2)
	a = makear(f)[:]
	a.append(a.pop(0))
	for i in range(f):
		a.append(a[i] + f)
	return a
n = int(input())
for e in maxlist(n):
	print(e, end=' ')
print()
print(n, end=' ')
if n != 1:
	for i in range(1, n):
		print(i, end=' ')


def shift(l, n):
	return l[n:] + l[:n]
t = int(input())
l = []
for i in range(1, t + 1):
	l.append(i)
n = t // 2
x = []
y = []
for i in range(1, n + 1):
	x.append(i)
for j in range(n + 1, t + 1):
	y.append(j)
x = shift(x, 1)
y = shift(y, 1)
x.extend(y)
for i in range(t):
	print(x[i], end=' ')
print(' ')
print(l[t - 1], end=' ')
for i in range(t - 1):
	print(l[i], end=' ')


n = int(input().strip())
if n == 2:
	min_list = [1, 2]
	max_list = [2, 1]
else:
	mid_elem = n // 2
	max_list = list(range(2, mid_elem + 1))
	max_list.append(1)
	max_list.extend(list(range(mid_elem + 2, n + 1)))
	max_list.append(mid_elem + 1)
	min_list = [n]
	min_list.extend(list(range(1, n)))
print(*max_list, sep=' ')
print(*min_list, sep=' ')


n = int(input())
a = [-1] * n
if n is 1:
	print(n)
	print(n)
elif n is 2:
	print('1 2')
	print('2 1')
else:
	k = n // 2
	a[k - 1] = 1
	if k - 1 != 0:
		a[0] = 2
	l = 3
	for m in range(1, k - 1):
		a[m] = l
		l += 1
	a[k] = k + 2
	a[-1] = k + 1
	l = k + 3
	for m in range(k + 1, n - 1):
		a[m] = l
		l += 1
	for i in a:
		print(i, end=' ')
	print()
	a[0] = n
	for i in range(1, n):
		a[i] = i
	for i in a:
		print(i, end=' ')


n = int(input())
ma = [i for i in range(2, 2 + (n - 1) // 2)] + [1] + [j for j in range(3 + (n - 1) // 2, n + 1)] + [2 + (n - 1) // 2]
mi = [n] + [i for i in range(1, n)]
print(*ma)
print(*mi)


p = [None, [1], [2, 1], [1, 3, 2], [2, 1, 4, 3], [2, 1, 4, 5, 3], [2, 3, 1, 5, 6, 4], [2, 3, 1, 5, 6, 7, 4], [2, 3, 4, 1, 6, 7, 8, 5], [2, 3, 4, 1, 6, 7, 8, 9, 5], [2, 3, 4, 5, 1, 7, 8, 9, 10, 6], [2, 3, 4, 5, 1, 7, 8, 9, 10, 11, 6], [2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 12, 7], [2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 12, 13, 7], [2, 3, 4, 5, 6, 7, 1, 9, 10, 11, 12, 13, 14, 8], [2, 3, 4, 5, 6, 7, 1, 9, 10, 11, 12, 13, 14, 15, 8], [2, 3, 4, 5, 6, 7, 8, 1, 10, 11, 12, 13, 14, 15, 16, 9], [2, 3, 4, 5, 6, 7, 8, 1, 10, 11, 12, 13, 14, 15, 16, 17, 9]]
n = int(input())
b = [(i + n - 1) % n + 1 for i in range(n)]
print(' '.join(map(str, p[n])))
print(' '.join(map(str, b)))


n = int(input())
s = ''
if n == 1:
	print('1\n1\n')
else:
	mid = n // 2
	for i in range(1, mid):
		s += str(i + 1) + ' '
	s += '1' + ' '
	for j in range(mid + 1, n):
		s += str(j + 1) + ' '
	s += str(mid + 1)
	p = ''
	p += str(n)
	for i in range(1, n):
		p += ' ' + str(i)
print(s)
print(p)


import math
import time
import string
import itertools
import operator
import functools
n = int(input().strip())
l = [i for i in range(1, n + 1)]
(l1, l2) = ([], [])
if n == 1:
	print(1)
	print(1)
elif n == 2:
	print(2, 1)
	print(2, 1)
elif n == 3:
	print(2, 3, 1)
	print(3, 1, 2)
else:
	x = int(math.ceil(n / 2))
	l1 = [i for i in range(2, x + 1)]
	l1.append(1)
	l1 = l1 + [i for i in range(x + 2, n + 1)]
	l1.append(x + 1)
	l2.append(n)
	l2 = l2 + [i for i in range(1, n)]
	print(*l1)
	print(*l2)