For his birthday, Kevin received the set of pairwise distinct numbers $1, 2, 3, \ldots, n$ as a gift.

He is going to arrange these numbers in a way such that the minimum absolute difference between two consecutive numbers be maximum possible. More formally, if he arranges numbers in order $p_1, p_2, \ldots, p_n$, he wants to maximize the value $$\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert,$$ where $|x|$ denotes the absolute value of $x$.

Help Kevin to do that.


-----Input-----

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Description of the test cases follows.

The only line of each test case contains an integer $n$ ($2 \le n \leq 1000$) — the size of the set.


-----Output-----

For each test case print a single line containing $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) describing the arrangement that maximizes the minimum absolute difference of consecutive elements.

Formally, you have to print a permutation $p$ which maximizes the value $\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert$.

If there are multiple optimal solutions, print any of them.


-----Examples-----

Input
2
4
3
Output
2 4 1 3
1 2 3


-----Note-----

In the first test case the minimum absolute difference of consecutive elements equals $\min \{\lvert 4 - 2 \rvert, \lvert 1 - 4 \rvert, \lvert 3 - 1 \rvert \} = \min \{2, 3, 2\} = 2$. It's easy to prove that this answer is optimal.

In the second test case each permutation of numbers $1, 2, 3$ is an optimal answer. The minimum absolute difference of consecutive elements equals to $1$.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Mathematics

Constructive algorithms


Solutions:
from math import floor, ceil
tc = int(input())
while tc > 0:
	setSize = int(input())
	halfSize = setSize / 2
	up = floor(halfSize)
	down = ceil(halfSize)
	a = [down]
	if setSize % 2 == 0:
		down += 1
	for i in range(1, setSize):
		if i % 2 == 0:
			a.append(a[-1] - down)
		else:
			a.append(a[-1] + up)
	print(' '.join(map(str, a)))
	tc -= 1


n = int(input())
for j in range(n):
	a = int(input())
	ans = ''
	first = a // 2
	last = a
	if a <= 3:
		for i in range(a):
			ans += str(i + 1) + ' '
		print(ans[:-1])
	elif a % 2 == 0:
		for i in range(first, 0, -1):
			ans += str(i) + ' ' + str(last) + ' '
			last -= 1
		print(ans[:-1])
	elif a % 2 != 0:
		last = a - 1
		for i in range(first, 0, -1):
			ans += str(i) + ' ' + str(last) + ' '
			last -= 1
		print(f'{a} {ans}')


import math

def solve():
	n = int(input())
	a1 = [i for i in range(1, math.ceil(n / 2) + 1)]
	a2 = [i for i in range(math.ceil(n / 2) + 1, n + 1)]
	i = 0
	j = 0
	if len(a1) == len(a2):
		(a1, a2) = (a2, a1)
	arr = []
	for k in range(n):
		if k % 2 == 0:
			arr.append(a1[i])
			i += 1
		else:
			arr.append(a2[j])
			j += 1
	print(' '.join(map(str, arr)))
t = int(input())
while t:
	t -= 1
	solve()


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n):
	diff = n // 2
	out = []
	for i in range(1, n // 2 + 1):
		out.append(i + diff)
		out.append(i)
	if n // 2 != n / 2:
		out = [n] + out
	print(' '.join(map(str, out)))
t = ni()
for case in range(t):
	n = ni()
	solve(n)


for _ in range(int(input())):
	n = int(input())
	if n < 4:
		for i in range(n):
			print(i + 1, end=' ')
		print()
		continue
	a = []
	if n % 2 == 0:
		for i in range(n // 2, 0, -1):
			a.append(str(i))
			a.append(str(i + n // 2))
	else:
		a.append(str(n))
		for i in range(n // 2, 0, -1):
			a.append(str(i))
			a.append(str(i + n // 2))
	print(' '.join(a))


testcases = int(input())
for _ in range(testcases):
	n = int(input())
	first_half = [i + 1 for i in range(n // 2)]
	second_half = [i for i in range(n // 2 + 1, n + 1)]
	answer = []
	for (i, j) in zip(first_half, second_half):
		answer.append(str(j))
		answer.append(str(i))
	if len(first_half) != len(second_half):
		answer.append(str(n))
	print(' '.join(answer))


t = int(input())
for i in range(t):
	n = int(input())
	mid = n // 2
	j = 1
	k = mid + 1
	ret = ''
	for a in range(mid):
		ret += f'{k} {j} '
		k += 1
		j += 1
	if n % 2 != 0:
		ret += str(n)
	print(ret)


def solve(n):
	i = 1
	j = n // 2 + 1
	s = ''
	while i < n // 2 + 1:
		s += f'{j} {i} '
		i += 1
		j += 1
	if n % 2 == 1:
		s += f'{n}'
	return s
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	print(solve(n))


test = int(input())
for t in range(test):
	num = int(input())
	a = []
	for i in range(1, (num - 1) // 2 + 1):
		a.append(i)
		a.append(i + num // 2 + 1)
	if num % 2 == 0:
		a.insert(0, num // 2 + 1)
		a.append(num // 2)
	else:
		a.insert(0, num // 2 + 1)
	print(' '.join(map(str, a)))


for _ in range(int(input())):
	n = int(input())
	diff = n // 2
	if n % 2 == 0:
		i = n // 2
	else:
		i = n // 2 + 1
	res = []
	while i > 0:
		res.append(str(i))
		res.append(str(i + diff))
		i -= 1
	if n % 2 == 0:
		print(' '.join(res))
	else:
		print(' '.join(res[:-1]))


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		x = n // 2
		y = n
		for j in range(n // 2):
			print(x, y, end=' ')
			x -= 1
			y -= 1
	else:
		x = n // 2 + 1
		y = n
		for j in range(n // 2):
			print(x, y, end=' ')
			x -= 1
			y -= 1
		print(1)
	print()


tc = int(input())
for _ in range(tc):
	n = int(input())
	res = []
	if n % 2 == 0:
		even = 1
		odd = 0
	else:
		even = 0
		odd = 1
	first = n // 2
	second = n
	if odd == 1:
		first += 1
	for x in range(first):
		if first == 1 and odd == 1:
			res.append(str(first))
		else:
			res.append(str(first))
			res.append(str(second))
			first -= 1
			second -= 1
	print(' '.join(res))


def solve(n):
	r = {}
	for p in range(n, n // 2, -1):
		r[p - n // 2] = True
		r[p] = True
	return ' '.join((str(p) for p in r.keys()))

def main():
	for t in range(int(input())):
		n = int(input())
		print(solve(n))
main()


n = int(input())
for e in range(n):
	nb = int(input())
	l = []
	h = nb // 2
	if nb % 2 == 0:
		for i in range(h, 0, -1):
			l.append(i)
			l.append(i + h)
		print(' '.join(map(str, l)))
	else:
		for i in range(h + 1, 0, -1):
			l.append(i)
			l.append(i + h)
		print(' '.join(map(str, l[:-1])))


t = int(input())
for _ in range(t):
	n = int(input())
	nums = [i for i in range(1, n + 1)]
	half = len(nums[::2]) - 1
	(nums[::2], nums[1::2]) = (nums[half::-1], nums[:half:-1])
	print(*nums)


for _ in range(int(input())):
	n = int(input())
	start = n // 2 + 1
	res = []
	for i in range(1, n // 2 + 1):
		res.append(start + i - 1)
		res.append(i)
	if n % 2 != 0:
		res.append(n)
	print(' '.join(map(str, res)))


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	j = 0
	while j < (n + 1) // 2:
		l.append(str((n + 1) // 2 - j))
		j += 1
		if j <= n // 2:
			l.append(str(n - j + 1))
	print(' '.join(l))


for _ in range(int(input())):
	n = int(input().rstrip())
	mid = int(n / 2)
	result = []
	if n % 2 == 1:
		start = n - 1
	else:
		start = n
	for i in range(start, mid, -1):
		result.append(i - mid)
		result.append(i)
	if n % 2 == 1:
		result.append(n)
	print(' '.join(map(str, result)))


def min_diff_odd(n):
	mid = n // 2 + 1
	res = []
	for i in range(mid):
		res.append(i + 1)
		res.append(i + mid + 1)
	res.pop()
	return res

def min_diff_even(n):
	mid = n // 2
	res = []
	for i in range(mid):
		res.append(i + 1 + mid)
		res.append(i + 1)
	return res

def min_diff(n):
	if n % 2 == 0:
		return min_diff_even(n)
	return min_diff_odd(n)
cases = [int(input()) for _ in range(int(input()))]
for n in cases:
	print(' '.join(map(str, min_diff(n))))


def solve(n):
	if n == 2:
		return [1, 2]
	if n % 2 == 0:
		maxmin = n // 2
	else:
		maxmin = (n - 1) // 2
	arr = []
	for i in range(n - maxmin, 0, -1):
		arr.append(i)
		if i != 1 or n % 2 == 0:
			arr.append(i + maxmin)
	return arr
t = int(input())
for tt in range(t):
	n = int(input())
	arr = solve(n)
	print(' '.join([str(j) for j in arr]))


def solve(n):
	A = [e for e in range(1, n + 1)]
	A1 = A[:len(A) // 2]
	A2 = A[len(A) // 2:]
	res = []
	for i in range(min(len(A1), len(A2))):
		res.append(A2[i])
		res.append(A1[i])
	if len(A) % 2:
		res.append(A2[len(A2) - 1])
	return ' '.join([str(e) for e in res])

def main():
	for _ in range(int(input())):
		n = int(input())
		print(solve(n))
main()


z = int(input())
for i in range(z):
	n = int(input())
	max_value = int(n / 2)
	output = ''
	if n % 2 == 0:
		for j in range(max_value, 0, -1):
			output += str(j)
			output += ' '
			output += str(j + max_value)
			output += ' '
		print(output.rstrip())
	else:
		for j in range(max_value + 1, 1, -1):
			output += str(j)
			output += ' '
			output += str(j + max_value)
			output += ' '
		output += '1'
		print(output)


a = int(input())
for i in range(a):
	q = int(input())
	t = []
	for j in range(q // 2):
		t.append(str(q // 2 + 1 + j))
		t.append(str(j + 1))
	if q % 2 != 0:
		t.append(str(q))
	print(' '.join(t))


for _ in range(int(input())):
	n = int(input())
	p = []
	if n % 2:
		p.append(n)
	m = n // 2
	for i in range(n // 2):
		p.append(i + m + 1)
		p.append(i + 1)
	print(' '.join(map(lambda x: str(x), list(p))))


n = input()
p = []
for i in range(0, int(n)):
	l = input()
	p.append(int(l))
for i in p:
	t = ''
	n = 1
	for j in range(0, i // 2):
		p = f'{n} {n + i // 2} '
		n = n + 1
		t = p + t
	if i % 2 == 0:
		print(t)
	else:
		print(f'{i} ' + t)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(j + 1) for j in range(n)]
	b = []
	if n % 2 == 0:
		for k in range(int(n / 2) + 1, n + 1):
			b.append(k)
			b.append(k - int(n / 2))
	else:
		for h in range(int((n + 1) / 2), n):
			b.append(h)
			b.append(h - int((n + 1) / 2) + 1)
		b.append(n)
	print(' '.join([str(x) for x in b]))


def solve(n):
	p = []
	if n % 2 == 1:
		p.append(str(n))
	mid = n // 2
	for i in range(mid, 0, -1):
		p.append(str(i))
		p.append(str(i + mid))
	return ' '.join(p)
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n))


def solve(n):
	d = n // 2 + 1
	array = [d]
	for i in range(1, d):
		array.extend((i, i + d))
	if n % 2 == 0:
		del array[-1]
	answer = ' '.join([str(x) for x in array])
	print(answer)
t = int(input())
for i in range(t):
	n = int(input())
	solve(n)


for _ in range(int(input())):
	n = int(input())
	smaller = [i for i in range(1, n // 2 + 1)] if n % 2 == 0 else [i for i in range(1, n // 2 + 2)]
	larger = [i for i in range(n // 2 + 1, n + 1)] if n % 2 == 0 else [i for i in range(n // 2 + 2, n + 1)]
	result = []
	while len(smaller) > 0 and len(larger) > 0:
		result.append(smaller.pop())
		result.append(larger.pop())
	result += smaller
	print(' '.join((str(i) for i in result)))


def f():
	n = int(input())
	for _ in range(n):
		L = int(input())
		half = L // 2 + 1
		res = []
		for i in range(L // 2):
			res.append(half + i)
			res.append(i + 1)
		if L % 2 == 1:
			res.append(L)
		print(' '.join([str(x) for x in res]))
f()


t = int(input())
for i in range(t):
	n = int(input())
	ans = []
	d = int(n / 2)
	for i in range(d, 0, -1):
		ans.append(i)
		ans.append(i + d)
	if n % 2:
		ans.append(n)
	print(' '.join((str(x) for x in ans)))


t = int(input())
for x in range(t):
	n = int(input())
	l = []
	x = n // 2 + 1
	for i in range(n // 2):
		l.append(x + i)
		l.append(i + 1)
	if n % 2 != 0:
		l.append(n)
	print(' '.join(map(str, l)))


runs = int(input())
for _ in range(runs):
	n = int(input())
	s = ''
	low = 1
	high = 1 + int(n / 2)
	if n % 2:
		while high < n:
			s += str(high) + ' '
			s += str(low) + ' '
			low += 1
			high += 1
		s += str(high) + ' '
	else:
		while high <= n:
			s += str(high) + ' '
			s += str(low) + ' '
			low += 1
			high += 1
	print(s[0:-1])


def out(n):
	out = ''
	if n % 2 == 0:
		for i in range(n // 2, 0, -1):
			out += str(i) + ' ' + str(i + n // 2) + ' '
	else:
		for i in range(1, (n + 1) // 2):
			out += str(i) + ' ' + str(i + (n + 1) // 2) + ' '
		out += str(n // 2 + 1)
	print(out)
t = int(input())
for i in range(t):
	n = int(input())
	out(n)


def main():
	t = int(input())
	for _ in range(t):
		solve()

def solve():
	n = int(input())
	x = n // 2
	if n % 2 != 0:
		x = (n + 1) // 2
	ans = [str(x)]
	(inc, dec) = (n // 2, -1)
	for i in range(1, n):
		if i % 2 != 0:
			ans.append(str(x + inc))
			inc -= 1
		else:
			ans.append(str(x + dec))
			dec -= 1
	print(' '.join(ans))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	max_len = n // 2
	a = [max_len + n % 2]
	for i in range(n - 1):
		if i % 2 == 0:
			a.append(a[i] + max_len)
		else:
			a.append(a[i] - max_len - 1)
	print(' '.join((str(i) for i in a)))


cases = int(input())
for _ in range(cases):
	case = int(input())
	output = []
	if case % 2 == 1:
		numbers = [str(i) for i in range(1, case + 1)]
		first_half = numbers[:int(case / 2) + 1][::-1]
		second_half = numbers[int(case / 2) + 1:][::-1]
	elif case % 2 == 0:
		numbers = [str(i) for i in range(1, case + 1)]
		first_half = numbers[:int(case / 2)][::-1]
		second_half = numbers[int(case / 2):][::-1]
	for i in range(len(second_half)):
		output.append(first_half[i])
		output.append(second_half[i])
	if case % 2 == 1:
		output.append(first_half[-1])
	print(' '.join(output))


k = int(input(''))
for j in range(k):
	n = int(input(''))
	s = ''
	if n % 2 == 0:
		for i in range(int(n / 2), 0, -1):
			s += str(i) + ' ' + str(int(i + n / 2)) + ' '
	else:
		for i in range(int(n / 2 + 1), 1, -1):
			s += str(i) + ' ' + str(int(i + n / 2)) + ' '
		s += '1'
	print(s)


def permutation(n):
	output = []
	if n <= 3:
		return [str(k) for k in range(1, n + 1)]
	if n % 2 == 1:
		i = 0
		while len(output) < n:
			output.append(str(i + 1))
			i = (i + n // 2) % n
	else:
		done = {1: 1, n // 2 + 1: n // 2 + 1, n // 2: n // 2, n: n}
		i = n // 2 - 1
		while len(done) != n:
			output.append(str(i))
			output.append(str(i + n // 2))
			done[i] = i
			done[i + n // 2] = i + n // 2
			i -= 1
		output = [str(n // 2), str(n)] + output + ['1', str(n // 2 + 1)]
	return output

def main():
	number = int(input())
	sets = []
	for _ in range(number):
		sets.append(int(input()))
	output = ''
	for k in enumerate(sets):
		perm = permutation(int(k[1]))
		print(' '.join(perm))
main()


def lister(n):
	L = []
	k = n // 2
	for i in range(k):
		L.append(str(k + 1 + i))
		L.append(str(1 + i))
	if n % 2 == 1:
		L.append(str(n))
	return L

def main():
	NumTests = int(input())
	for i in range(NumTests):
		n = int(input())
		print(' '.join(lister(n)))
main()


for _ in range(int(input())):
	n = int(input())
	r = ''
	l = n // 2 + 1
	for i in range(n // 2):
		r += f'{i + l} {i + 1} '
	if n % 2 != 0:
		r += f'{n}'
	print(r)


import itertools
import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve(n):
	if n <= 3:
		print(' '.join(list(map(str, range(1, n + 1)))))
		return
	arr = []
	length_of_each = n // 2
	if n % 2 == 0:
		for i in range(1, length_of_each + 1):
			arr += [length_of_each + i, i]
	else:
		for i in range(1, length_of_each + 1):
			arr += [i, length_of_each + 1 + i]
	if n % 2 == 1:
		arr.insert(0, str(n // 2 + 1))
	print(' '.join(list(map(str, arr))))
for i in range(inp()):
	n = inp()
	solve(n)


import math
t = int(input())
for i in range(t):
	n = int(input())
	ans = []
	seq = range(1, n + 1)
	if n < 4:
		g = list(seq)
		(g[0], g[1]) = (g[1], g[0])
		print(' '.join([str(x) for x in g]))
	elif n % 2 == 0:
		for j in range(math.floor(n / 2 - 1), -1, -1):
			a = seq[j]
			b = seq[math.floor(j + n / 2)]
			x = [str(a), str(b)]
			ans += x
	else:
		for j in range(math.floor((n + 1) / 2 - 1), 0, -1):
			a = seq[j]
			b = seq[math.floor(j + (n - 1) / 2)]
			x = [str(a), str(b)]
			ans += x
		ans += [str(seq[0])]
	print(' '.join(ans))


for i in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		p = n // 2
		a = ''
		for i in range(p):
			a = a + str(n - p) + ' ' + str(n) + ' '
			n -= 1
	else:
		p = n // 2
		a = f'{n} '
		n -= 1
		for i in range(p):
			a = a + str(n - p) + ' ' + str(n) + ' '
			n -= 1
	print(a[:-1])


import math

def main():
	result = []
	t = int(input())
	for test in range(t):
		n = int(input())
		half_n = math.floor(n / 2)
		permutation = []
		for i in range(half_n):
			i += 1
			permutation.append(str(half_n + i))
			permutation.append(str(i))
		if n % 2 != 0:
			permutation.append(str(n))
		result.append(' '.join(permutation))
	print(*result, sep='\n')
main()


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(n):
	if n == 3:
		return [1, 2, 3]
	m = n // 2 + 1
	a = list(range(m, n + 1))
	b = list(range(1, m))
	(i, j) = (0, 0)
	ans = []
	while i < len(a) and j < len(b):
		ans.append(a[i])
		ans.append(b[j])
		i += 1
		j += 1
	if i < len(a):
		ans.append(a[i])
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	print(' '.join((str(x) for x in solve(n))))


from math import ceil

def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'er9fj48gh48gh4' == 14194665565:
		print('Tanmay')
	if n < 4:
		for i in range(n):
			print(i + 1, end=' ')
		print()
		continue
	ans = [0] * n
	x = 1
	for i in range(1, n, 2):
		ans[i] = x
		x += 1
	for i in range(0, n, 2):
		ans[i] = x
		x += 1
	a = ''
	for i in ans:
		a += str(i) + ' '
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	if n <= 3:
		for i in range(n):
			print(i + 1, end=' ')
		print()
		continue
	if n % 2 == 0:
		x = n // 2
		for i in range(x):
			print(x + i + 1, i + 1, end=' ')
		print()
	else:
		n -= 1
		x = n // 2
		for i in range(x):
			print(x + i + 1, i + 1, end=' ')
		print(n + 1)


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


n_tests = int(input())
for _ in range(n_tests):
	n = int(input())
	i = n // 2 + n % 2
	j = n
	while i > 0:
		print(i, end=' ')
		if i != 1 or n % 2 != 1:
			print(j, end=' ')
		i = i - 1
		j = j - 1
	print()


n = int(input())
for x in range(n):
	m = int(input())
	if m % 2 == 0:
		for i in range(m // 2):
			print(i + 1 + m // 2, end=' ')
			print(i + 1, end=' ')
		print('')
	else:
		print(1, end=' ')
		for i in range(m // 2):
			print(m // 2 + 1 - i, end=' ')
			print(m - i, end=' ')
		print('')


samples = int(input())
for i in range(samples):
	n = int(input())
	if n % 2 == 0:
		for j in range(n // 2 - 1):
			print(n // 2 - j, end=' ')
			print(n - j, end=' ')
		print(1, end=' ')
		print(n // 2 + 1, end='\n')
	else:
		for k in range((n + 1) // 2 - 1):
			print((n + 1) // 2 - k, end=' ')
			print(n - k, end=' ')
		print(1, end='\n')


tests = int(input())
for i in range(tests):
	n = int(input())
	outputlist = []
	if n % 2 == 0:
		larger = n
		smaller = n // 2
		while smaller > 0:
			outputlist.append(str(smaller))
			outputlist.append(str(larger))
			larger -= 1
			smaller -= 1
		print(' '.join(outputlist))
	else:
		outputlist.append(str((n + 1) // 2))
		larger = n
		smaller = (n - 1) // 2
		while smaller > 0:
			outputlist.append(str(larger))
			outputlist.append(str(smaller))
			larger -= 1
			smaller -= 1
		print(' '.join(outputlist))


def sol(n1):
	dt = [0] * n1
	dt3 = [0] * n1
	c = 0
	(i, cnt) = (0, 0)
	h = n1 // 2 + 1
	for i in range(0, n1 // 2):
		dt[i * 2] = i + 1
		if h + dt[i * 2] <= n1:
			dt[i * 2 + 1] = h + dt[i * 2]
	if n1 + 1 % 2:
		dt3[1:0] = dt
		dt3[0] = h
		dt = dt3[0:n1]
	return dt
	dt2 = dt * 2
	f = check(n1, dt)
	dx = dt2[h:n1 + h]
	b = check(n1, dx)
	if f > b:
		return dt
	else:
		return dx

def check(n1, dt):
	sol = []
	mn = n1 + 1
	for i in range(n1 - 1):
		mn = min(mn, abs(dt[i + 1] - dt[i]))
	return mn
n = input()
for i in range(int(n)):
	t = int(input())
	dt = sol(t)
	ans = str(dt[0])
	for i in dt[1:]:
		ans += ' ' + str(i)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	res = [None] * n
	mi = (n + 2) // 2
	res[1::2] = range(1, mi)
	res[::2] = range(mi, n + 1)
	print(*res)


t = int(input())
for i in range(t):
	n = int(input())
	ans = n // 2
	if n % 2 == 0:
		ans = n // 2
		for j in range(n // 2, 0, -1):
			print(j, j + ans, end=' ')
	else:
		for j in range(n // 2 - 1, -1, -1):
			for k in range(j, n, ans):
				print(k + 1, end=' ')
	print()


T = int(input())
for k in range(T):
	N = int(input())
	if N & 1 == 0:
		X = N // 2
		K = N
		ans = []
		for i in range(N // 2):
			ans.append(str(X))
			ans.append(str(K))
			X -= 1
			K -= 1
	else:
		X = N // 2
		K = N - 1
		ans = []
		for i in range(N // 2):
			ans.append(str(X))
			ans.append(str(K))
			X -= 1
			K -= 1
		ans.append(str(N))
	print(' '.join(ans))


n = int(input())
for i in range(n):
	m = int(input())
	k = (m + 1) // 2
	l = abs(k - m)
	s = ''
	if m % 2 == 1:
		for j in range(1, m // 2 + 1):
			x = j + l
			s = s + str(x) + ' '
			s += str(j) + ' '
		s += str(m)
		print(s)
	else:
		for j in range(1, m // 2 + 1):
			x = j + l
			s = s + str(x) + ' '
			s += str(j) + ' '
		print(s)


a = int(input())
for i in range(a):
	b = int(input())
	c = ''
	if b % 2 == 0:
		for j in range(0, b // 2):
			k = b // 2 - j
			m = b - j
			if k != 1:
				c = c + str(k) + ' ' + str(m) + ' '
			else:
				c = c + str(k) + ' ' + str(m)
	else:
		for j in range(0, b // 2 + 1):
			k = b // 2 + 1 - j
			m = b - j
			if k != 1:
				c = c + str(k) + ' ' + str(m) + ' '
			else:
				c = c + str(k)
	print(c)


for _ in range(int(input())):
	n = int(input())
	x = 0
	y = 0
	s = []
	if n % 2 == 0:
		x = [i for i in range(1, n // 2 + 1)]
		y = [i for i in range(n // 2 + 1, n + 1)]
	else:
		x = [i for i in range(1, n // 2 + 1)]
		y = [i for i in range(n // 2 + 1, n + 1)]
	y = y[::-1]
	x = x[::-1]
	if len(x) == len(y):
		for i in range(len(x)):
			s.append(x[i])
			s.append(y[i])
	else:
		s.append(y[0])
		y = y[1:]
		for i in range(len(y)):
			s.append(x[i])
			s.append(y[i])
	print(*s)


kolvo = int(input())
for i in range(kolvo):
	length = int(input())
	if length % 2 == 0:
		A = list(range(1, length + 1))
		B = A[:len(A) // 2]
		C = A[len(A) // 2:]
		B = list(reversed(B))
		C = list(reversed(C))
		ANS = list()
		for i in range(length // 2):
			ANS.append(B[i])
			ANS.append(C[i])
		ans = ' '.join((str(x) for x in ANS))
		print(ans)
	else:
		A = list(range(1, length + 1))
		B = A[:len(A) // 2]
		C = A[len(A) // 2:]
		B = list(reversed(B))
		C = list(reversed(C))
		ANS = list()
		for i in range(length // 2):
			ANS.append(C[i])
			ANS.append(B[i])
		ANS.append(len(A) // 2 + 1)
		ans = ' '.join((str(x) for x in ANS))
		print(ans)


t = int(input())

def maxDiff(n):
	jump = n // 2
	if n % 2 == 1:
		prev = 1
		for i in range(n):
			if prev % n == 0:
				print(n, end=' ')
			else:
				print(prev % n, end=' ')
			prev += jump
	else:
		for i in range(jump, 0, -1):
			print(i, i + jump, end=' ')
	print()
for i in range(t):
	n = int(input())
	maxDiff(n)


for i in range(int(input())):
	num = int(input())
	re = []
	half = num // 2
	for i in range(1, half + 1):
		re.append(half + i)
		re.append(i)
	if num % 2:
		re.append(num)
	print(*re)


t = int(input())
for _ in range(t):
	n = int(input())
	x = 1
	a = [0] * n
	for i in range(1, n, 2):
		a[i] = x
		x += 1
	for i in range(0, n, 2):
		a[i] = x
		x += 1
	_str = ''
	for i in a:
		_str += str(i) + ' '
	print(_str)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n // 2, 0, -1):
		l.extend((i, i + n // 2))
	if n % 2 != 0:
		l.append(n)
	print(*l)


for n in map(int, [*open(0)][1:]):
	print(*[(n - i - 1) // 2 + 1 + i % 2 * (n // 2 + n % 2) for i in range(n)])


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	if n % 2 == 1:
		l.append(n)
	start = n // 2 + 1
	if n % 2 == 1:
		n -= 1
	low = n // 2
	high = n // 2 + 1
	cnt = 0
	for i in range(n):
		l.append(start)
		if cnt == 0:
			start = (start + low) % n
		else:
			start = (start + high) % n
		if start == 0:
			start = n
		cnt = 1 - cnt
	print(*l)


n = int(input())
for i in range(n):
	x = int(input())
	d = x // 2
	for j in range((x + 1) // 2, 1, -1):
		print(j, j + d, end=' ')
	if x % 2 == 0:
		print(1, 1 + d)
	else:
		print(1)


for i in range(int(input())):
	n = int(input())
	f = 0
	for j in range(n // 2):
		if n % 2 == 1:
			print(n // 2 - f + 1, n - f, end=' ')
		else:
			print(n // 2 - f, n - f, end=' ')
		f += 1
	if n % 2 == 1:
		print(1)
	else:
		print('')


n = int(input())
if 1 <= n and n <= 100:
	for i in range(n):
		k = int(input())
		lista = []
		if 2 <= k and k <= 1000:
			if k % 2 == 0:
				for i in range(int(k / 2)):
					lista.append(k - int(k / 2) - i)
					lista.append(k - i)
				print(' '.join(map(str, lista)))
			else:
				lista.append(1)
				for i in range(int(k / 2)):
					lista.append(int((k + 1) / 2) - i)
					lista.append(k - i)
				print(' '.join(map(str, lista)))


n = int(input())
from sys import stdin, stdout
while n > 0:

	def order(n):
		out = []
		(lo, hi) = (n // 2, n)
		if n % 2 == 1:
			lo += 1
		while lo != 0:
			out += [lo]
			lo -= 1
			if lo == 0:
				break
			out += [hi]
			hi -= 1
		if n % 2 == 0:
			out += [hi]
		print(' '.join([str(x) for x in out]))
	order(int(input()))
	n -= 1


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		if i % 2 == 1:
			v = n
		else:
			v = n - n // 2
		a.append(v - i // 2)
	print(*a)


def helper(s):
	start = s // 2 + 1
	ans = [start]
	diff = start - 1
	c = 1
	v = set([start])
	while c < s:
		if c % 2 == 1:
			d = -diff
		if c % 2 == 0:
			d = diff + 1
		start += d
		if start in v or not 1 <= start <= s:
			return 1
		ans.append(start)
		v.add(start)
		c += 1
	return ' '.join(list(map(str, ans)))
for i in range(int(input())):
	print(helper(int(input())))


for i in range(int(input())):
	b = int(input())
	s = ''
	j = b // 2
	while j != 0:
		s = s + str(j) + ' ' + str(j + b // 2) + ' '
		j -= 1
	if b % 2 == 1:
		s += str(b)
	print(s)


case = int(input())
for _ in range(case):
	no = int(input())
	if no < 4:
		for i in range(no):
			print(i + 1, end=' ')
	elif no % 2 == 0:
		n = int(no / 2)
		for j in range(n, 0, -1):
			print(j, end=' ')
			print(j + n, end=' ')
		print()
	else:
		n = int((no - 1) / 2)
		for j in range(n, 0, -1):
			print(j, end=' ')
			print(j + n, end=' ')
		print(no, end=' ')
		print()


def getint():
	return int(input())

def getfloat():
	return float(input())

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

def getfloats():
	return list(map(float, input().split()))
T = getint()
for i in range(T):
	n = getint()
	ans = []
	if n % 2 == 0:
		for j in range(n // 2, 0, -1):
			ans.append(str(j))
			ans.append(str(j + n // 2))
	else:
		ans.append(str(n // 2 + 1))
		for j in range(n // 2, 0, -1):
			ans.append(str(j + n // 2 + 1))
			ans.append(str(j))
	print(' '.join(ans))


def main():
	n = int(input())
	for i in range(n // 2, 0, -1):
		print(f'{i} {i + n // 2} ', end='')
	if n % 2 == 1:
		print(n)
	else:
		print()
for _ in range(int(input())):
	main()


for m in map(int, [*open(0)][1:]):
	print(*[(m - i - 1) // 2 + 1 + i % 2 * (m // 2 + m % 2) for i in range(m)])


cases = int(input())
outputs = []
for i in range(cases):
	n = int(input())
	numbers = [i for i in range(1, n + 1)]
	outputString = ''
	if len(numbers) % 2 == 0:
		mid = n // 2
		while mid >= 1:
			outputString += str(numbers[mid - 1]) + ' '
			outputString += str(numbers[n - 1]) + ' '
			mid -= 1
			n -= 1
	else:
		mid = n // 2
		outputString += str(numbers[n - 1]) + ' '
		while mid >= 1:
			outputString += str(numbers[mid - 1]) + ' '
			outputString += str(numbers[n - 2]) + ' '
			mid -= 1
			n -= 1
	outputString.strip()
	outputs.append(outputString)
for i in range(len(outputs)):
	print(outputs[i])


n = int(input())
for _ in range(n):
	m = int(input())
	a = []
	b = []
	res = []
	for i in range(1, (m + 1) // 2 + 1):
		a.append(i)
	for j in range(int(m + 1) // 2 + 1, m + 1):
		b.append(j)
	if m % 2 == 0:
		for k in range(m // 2):
			res.append(b[k])
			res.append(a[k])
	else:
		for l in range(m // 2):
			res.append(a[l])
			res.append(b[l])
		res.append(a.pop())
	print(*res)


for _ in range(int(input())):
	n = int(input())
	mid = n // 2 + 1
	if n & 1 == 1:
		print(n, end=' ')
	for i in range(1, mid):
		print(mid, end=' ')
		print(i, end=' ')
		mid += 1
	print()


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


n = int(input())
for i in range(n):
	m = int(input())
	if m <= 3:
		for i in range(1, m + 1):
			print(i, end=' ')
	elif m == 4:
		print(2, 4, 1, 3, sep=' ')
	else:
		i = m // 2
		j = 0
		a = []
		while i != m:
			i += 1
			j += 1
			a.append(i)
			a.append(j)
		if m % 2 != 0:
			a.pop(-1)
		print(*a)


t = int(input())
for i in range(t):
	p = int(input())
	l = []
	for j in range(1, p + 1):
		l.append(j)
	l1 = []
	l2 = []
	l3 = []
	if p % 2 == 0:
		l1 = l[:p // 2]
		l2 = l[p // 2:]
		for k in range(len(l1)):
			l3.append(l2[k])
			l3.append(l1[k])
	else:
		l1 = l[:p // 2]
		l2 = l[p // 2 + 1:]
		for k in range(len(l1)):
			l3.append(l1[k])
			l3.append(l2[k])
		l3.insert(0, l[p // 2])
	l3 = ' '.join(map(str, l3))
	print(l3)


n = int(input())
for k in range(n):
	n = int(input())
	bottom_half = list(range(1, n // 2 + 1))
	top_half = list(range(n // 2 + 1, n + 1))
	answer = []
	j = 0
	k = 0
	for i in range(n):
		if i % 2 == 0:
			answer.append(top_half[j])
			j += 1
		else:
			answer.append(bottom_half[k])
			k += 1
	answer = ' '.join(map(str, answer))
	print(answer)


import math
test = int(input())
for i in range(test):
	inputs = int(input())
	listy = ''
	for i in range(inputs // 2):
		listy = listy + str(math.ceil(inputs / 2) - i) + ' '
		listy = listy + str(math.ceil(inputs / 2) - i + math.floor(inputs / 2)) + ' '
	if inputs % 2 == 1:
		listy += '1'
	print(listy)


t = int(input())
for i1 in range(t):
	n = int(input())
	s = [1 + n // 2, 1]
	for i in range(3, n + 1):
		if i == n and i % 2 != 0:
			s.append(n)
		else:
			s.append(s[-2] + 1)
	print(*s)


t = int(input(''))
a1 = []
for i in range(t):
	y = int(input(''))
	a1.append(y)
for j in range(t):
	a = a1[j]
	list = []
	if a % 2 == 0:
		first = a // 2
		last = a
		while last != a // 2:
			list.append(first)
			list.append(last)
			first -= 1
			last -= 1
	else:
		last = a - 1
		first = last // 2
		while last != (a - 1) // 2:
			list.append(first)
			list.append(last)
			first -= 1
			last -= 1
		list.append(a)
	for i in list:
		print(i, end=' ')
	print('')
	list.clear()