A permutation p of size n is the sequence p_1, p_2, ..., p_{n}, consisting of n distinct integers, each of them is from 1 to n (1 ≤ p_{i} ≤ n).

A lucky permutation is such permutation p, that any integer i (1 ≤ i ≤ n) meets this condition p_{p}_{i} = n - i + 1.

You have integer n. Find some lucky permutation p of size n.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the required permutation size.


-----Output-----

Print "-1" (without the quotes) if the lucky permutation p of size n doesn't exist.

Otherwise, print n distinct integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n) after a space — the required permutation.

If there are multiple answers, you can print any of them.


-----Examples-----
Input
1

Output
1 

Input
2

Output
-1

Input
4

Output
2 4 1 3 

Input
5

Output
2 5 3 1 4

Difficulty: MEDIUM
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
n = int(input())
if n % 4 > 1:
	print(-1)
else:
	a = [n + 1 >> 1] * n
	for i in range(n // 4):
		j = i * 2
		(a[j], a[j + 1], a[-2 - j], a[-1 - j]) = (j + 2, n - j, j + 1, n - 1 - j)
	print(' '.join(map(str, a)))


n = int(input())
L = [0] * (n + 1)
X = [False] * (n + 1)
if n % 4 != 0 and n % 4 != 1:
	print(-1)
else:
	for i in range(1, n + 1):
		if X[i]:
			continue
		X[i] = True
		X[n - i + 1] = True
		for j in range(i + 1, n + 1):
			if X[j]:
				continue
			X[j] = True
			X[n - j + 1] = True
			L[i] = j
			L[n - i + 1] = n - j + 1
			L[j] = n - i + 1
			L[n - j + 1] = i
			break
		if n % 4 == 1:
			L[n // 2 + 1] = n // 2 + 1
	for i in range(1, n):
		print(L[i], end=' ')
	print(L[n])


n = int(input())
if n % 4 == 2 or n % 4 == 3:
	print(-1)
else:
	ans = [0] * n
	for i in range(0, n // 2, 2):
		ans[i] = i + 2
		ans[i + 1] = n - i
		ans[n - i - 1] = n - i - 1
		ans[n - i - 2] = i + 1
	if n % 4 == 1:
		ans[n // 2] = n // 2 + 1
	print(*ans)


n = int(input())
if n == 1:
	print(1)
	return
if n % 4 > 1:
	print(-1)
	return
ans = [-1] * n
left = n
start = n - 2
nums = 1
nume = n
while left >= 4:
	ans[start] = nums
	ans[nums - 1] = nums + 1
	ans[nums] = nume
	ans[nume - 1] = nume - 1
	start -= 2
	nums += 2
	nume -= 2
	left -= 4
if left == 1:
	ans[start + 1] = start + 2
print(*ans)


n = int(input())
if n % 4 > 1:
	print(-1)
	return
a = [i for i in range(0, n + 1)]
for i in range(1, n // 2 + 1, 2):
	(p, q, r, s) = (i, i + 1, n - i, n - i + 1)
	(a[p], a[q], a[r], a[s]) = (a[q], a[s], a[p], a[r])

def check(arr):
	for i in range(1, n + 1):
		k = arr[i]
		if arr[arr[k]] != n - k + 1:
			return False
	return True
print(*a[1:])


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


n = int(input())
if n % 4 == 2 or n % 4 == 3:
	from sys import exit
	print(-1)
	exit()
(res, i) = ([0] * n, 0)
for i in range(0, n // 2, 2):
	(res[i], res[i + 1]) = (i + 2, n - i)
	(res[n - i - 1], res[n - i - 2]) = (n - i - 1, i + 1)
	i += 2
if n % 4 == 1:
	res[n // 2] = n // 2 + 1
print(*res)


import sys
usedNum = 0
n = int(input())
p = [0 for i in range(n + 1)]
usedNum = 0
if n % 4 == 3 or n % 4 == 2:
	print(-1)
else:
	i = 1
	j = n
	a = 1
	b = n
	while j > i:
		p[i] = a + 1
		p[i + 1] = b
		p[j] = b - 1
		p[j - 1] = a
		i += 2
		j -= 2
		a += 2
		b -= 2
	if j == i:
		p[i] = a
	ans = ''
	for i in range(1, n + 1):
		ans += str(p[i]) + ' '
	print(ans)


import sys
from collections import deque
n = int(input())
if n % 4 == 2 or n % 4 == 3:
	print('-1')
	return
arr = [None] * (n + 1)
qt = deque([i for i in range(1, n + 1)])
mark = set()
while qt:
	while qt and qt[0] in mark:
		qt.popleft()
	if not qt:
		break
	a = qt.popleft()
	while qt and qt[0] in mark:
		qt.popleft()
	if not qt:
		break
	b = qt.popleft()
	for i in range(4):
		mark.add(a)
		mark.add(b)
		arr[a] = b
		arr[b] = n - a + 1
		a = b
		b = arr[b]
for i in range(1, n + 1):
	if not arr[i]:
		arr[i] = a
		break
print(' '.join(map(str, arr[1:])))


from itertools import permutations
from sys import stdin

def checkit(vector, upto=-1):
	if upto == -1:
		upto = len(vector)
	for i in range(0, upto):
		if vector[vector[i] - 1] != len(vector) - (i + 1) + 1:
			return False
	return True

def calculate(n):
	numbers = list(range(1, n + 1))
	result = [0] * n
	for i in range(0, n):
		if result[i] != 0:
			continue
		if i > 0 and checkit(result, i):
			continue
		expected = n - i
		for v in numbers:
			if v - 1 == i and expected != v:
				continue
			if v == expected:
				result[v - 1] = v
				numbers.remove(v)
				break
			elif result[v - 1] == expected:
				numbers.remove(v)
				result[i] = v
				break
			elif result[v - 1] == 0:
				assert expected in numbers
				result[i] = v
				result[v - 1] = expected
				numbers.remove(v)
				numbers.remove(expected)
				break
	return result

def calculate_v2(n):
	result = [0] * n
	first_sum = n + 2
	second_sum = n
	nf = n
	i = 0
	while nf > first_sum // 2:
		result[i] = first_sum - nf
		result[i + 1] = nf
		nf -= 2
		i += 2
	if n % 2 == 1:
		result[i] = i + 1
	i = n - 1
	while i > n // 2:
		result[i] = i
		result[i - 1] = second_sum - i
		i -= 2
	return result

def main():
	number = int(stdin.readline())
	result = calculate_v2(number)
	if not checkit(result):
		print(-1)
	else:
		print(' '.join([str(v) for v in result]))
main()


n = int(input())
if n % 4 == 2 or n % 4 == 3:
	print(-1)
	return
(res, i) = ([0] * n, 0)
for i in range(0, n // 2, 2):
	(res[i], res[i + 1]) = (i + 2, n - i)
	(res[n - i - 1], res[n - i - 2]) = (n - i - 1, i + 1)
	i += 2
if n % 4 == 1:
	res[n // 2] = n // 2 + 1
print(*res)


n = int(input())
if n % 4 > 1:
	print(-1)
else:
	k = n // 2
	t = [0] * n
	for i in range(0, k, 2):
		t[i] = str(i + 2)
	for i in range(1, k, 2):
		t[i] = str(n - i + 1)
	if n & 1:
		k += 1
		t[k - 1] = str(k)
	for i in range(k, n, 2):
		t[i] = str(n - i - 1)
	for i in range(k + 1, n, 2):
		t[i] = str(i)
	print(' '.join(t))


n = int(input())
if n % 4 > 1:
	print(-1)
else:
	ans = [0] * (n + 1)
	(i, j, a, b) = (1, n, 1, n)
	while i < j and a <= n and (b >= 1):
		(ans[i], ans[j]) = (a + 1, b - 1)
		(ans[i + 1], ans[j - 1]) = (b, a)
		i += 2
		j -= 2
		a += 2
		b -= 2
	if i == j:
		ans[i] = a
	for i in range(1, n + 1):
		print(ans[i], end=' ')