A permutation p of size n is the sequence p1, p2, ..., pn, consisting of n distinct integers, each of them is from 1 to n (1 ≤ pi ≤ n).

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

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

Input

The first line contains integer n (1 ≤ n ≤ 105) — 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 p1, p2, ..., pn (1 ≤ pi ≤ 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())
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 > 1:
	print(-1)
	exit()
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 % 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))


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)


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)


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


from math import *
n = int(input())
if n == 1:
	print(1)
elif n % 4 in [2, 3]:
	print(-1)
else:
	ans = [0] * n
	for i in range(n // 2):
		if i & 1:
			ans[i] = n - 2 * (i // 2)
		else:
			ans[i] = 2 + i
	for i in range(1, n // 2, 2):
		ans[ans[i] - 1] = n - i
		ans[n - i - 1] = n - (n - i)
	if n % 4 < 3 and n % 4 > 0:
		ans[n // 2] = ceil(n / 2)
	elif n % 4 == 3:
		ans[int(floor(n / 2))] = ans[int(floor(n / 2)) - 1] + 1
		ans[int(ceil(n / 2))] = ans[int(ceil(n / 2)) - 1] - 2
	print(*ans)


n = int(input())
mod = n % 4
if mod == 2 or mod == 3:
	print(-1)
else:
	ans = [-1 for i in range(n)]
	i = 0
	while i < n // 2:
		ans[i] = n - i - 1
		ans[i + 1] = i + 1
		ans[n - 1 - i] = i + 2
		ans[n - 2 - i] = n - i
		i += 2
	if mod == 1:
		ans[n // 2] = n // 2 + 1
	print(' '.join(map(str, ans)))


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


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


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


import sys
from collections import deque
n = int(input())
if n % 4 == 2 or n % 4 == 3:
	print('-1')
	sys.exit()
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:])))


n = int(input())
p = [0] * n
if n == 1:
	print(1)
	exit()
for sh in range(n // 4):
	p[n - sh * 2 - 2] = n - sh * 2
	p[sh * 2] = n - 1 - sh * 2
	p[n - sh * 2 - 1] = 2 + sh * 2
	p[sh * 2 + 1] = 1 + sh * 2
if n % 4 == 1:
	p[n // 2] = n // 2 + 1
if n % 4 == 2:
	print(-1)
	exit()
if n % 4 == 3:
	print(-1)
	exit()
print(' '.join([str(i) for i in p]))


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def main():
	n = int(input())
	if n % 4 == 2 or n % 4 == 3:
		print(-1)
	else:
		a = deque(list(range(1, n + 1)))
		ans = [0] * n
		for i in range(0, n // 2, 2):
			ans[-(i + 2)] = a.popleft()
			ans[i] = a.popleft()
			ans[i + 1] = a.pop()
			ans[-(i + 1)] = a.pop()
		if a:
			ans[n // 2] = a.pop()
		print(*ans)
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))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
if n == 1:
	print(1)
	exit()
if n % 4 > 1:
	print(-1)
	exit()
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)