Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef Tobby asked Bhuvan to brush up his knowledge of statistics for a test. While studying some distributions, Bhuvan learns the fact that for symmetric distributions, the mean and the median are always the same.

Chef Tobby asks Bhuvan out for a game and tells him that it will utilize his new found knowledge. He lays out a total of 10^{9} small tiles in front of Bhuvan. Each tile has a distinct number written on it from 1 to 10^{9}.

Chef Tobby gives Bhuvan an integer N and asks him to choose N distinct tiles and arrange them in a line such that the mean of median of all subarrays lies between [N-1, N+1], both inclusive. The median of subarray of even length is the mean of the two numbers in the middle after the subarray is sorted

Bhuvan realizes that his book didn’t teach him how to solve this and asks for your help. Can you solve the problem for him?

In case, no solution exists, print -1.

------ Input section ------ 

First line contains, T, denoting the number of test cases.

Each of the next T lines, contain a single integer N.

------ Output section ------ 

If no solution, exists print -1.

If the solution exists, output N space separated integers denoting the elements of the array A such that above conditions are satisfied. In case, multiple answers exist, you can output any one them.

------ Input constraints ------ 

1 ≤ T ≤ 20
1 ≤ N ≤ 100

----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
1
1 2
1 2 3
----- explanation 1 ------ 
For test case 3, the subarrays and their median are as follows: 

{1}, median = 1
{2}, median = 2
{3}, median = 3
{1, 2}, median = 1.5
{2, 3}, median = 2.5
{1, 2, 3}, median = 2
The mean of the medians is 2 which lies in the range [2, 4]

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
def main():
	try:
		if n == 1:
			print(1)
		else:
			print(*range(n // 2, n + n // 2))
	except Exception as e:
		print(e)
t = int(input())
for _ in range(t):
	n = int(input())
	main()


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


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


for j in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		a = n // 2
		for i in range(a, a + n):
			print(i, end=' ')
	if n != 1:
		print()


from math import ceil

def fun(n):
	if n == 1:
		print(1)
		return
	ans = n / 2 + 0.5
	x = ceil(n - 1 - ans)
	seq = list(range(1 + x, 1 + x + n))
	print(*seq)
test = int(input())
for i in range(test):
	n = int(input())
	fun(n)


def solve(n, i):
	l = [i for i in range(i, i + n)]
	z = n * (n + 1) // 2
	sum = 0
	for i in range(n):
		la = []
		for j in range(i, n):
			la.append(l[j])
			if len(la) % 2 != 0:
				sum += la[(len(la) - 1) // 2]
			else:
				sum += (la[(len(la) - 1) // 2] + la[(len(la) - 1) // 2 + 1]) / 2
	k = sum / z
	if n - 1 <= k <= n + 1:
		return l
	else:
		return False
t = int(input())
for i in range(t):
	n = int(input())
	for i in range(1, 60):
		z = solve(n, i)
		if z != False:
			print(*z)
			break


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	if n == 2:
		print(1, 2)
		continue
	if n == 3:
		print(1, 2, 3)
		continue
	a = [0] * n
	idx = math.ceil((n + 1) / 2)
	a[idx - 1] = n
	j = 1
	for i in range(idx - 2, -1, -1):
		a[i] = n - j
		j += 1
	j = 1
	for i in range(idx, n):
		a[i] = n + j
		j += 1
	print(*a)


def solve(x):
	ret = ''
	if x == 1:
		return '1'
	if x % 2 == 1:
		s = x - 1
		ret = [s]
		for i in range(1, x // 2 + 1):
			ret = [s - i] + ret + [s + i]
	else:
		ret = []
		for i in range(x // 2):
			ret = [x - i - 1] + ret + [x + i]
	return ' '.join(map(str, ret))
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	x = int(f.readline())
	print(solve(x))


import math
t = int(input())
ans = []
for i in range(t):
	n = int(input())
	s = 1 + (n - 1) * 0.5
	if s >= n - 1:
		a = []
		for i in range(1, n + 1):
			a.append(i)
		ans.append(a)
	else:
		a = []
		d = n - 1 - s
		d = math.ceil(d)
		for i in range(1, n + 1):
			a.append(i + d)
		ans.append(a)
for b in ans:
	for i in b:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	l = int(input())
	k = (l + 1) / 2
	if l == 1:
		print(1)
	elif k <= l + 1 and k >= l - 1:
		for i in range(1, l + 1):
			print(i, end=' ')
		print()
	else:
		for i in range(1, l + 1):
			print(2 * i, end=' ')
		print()


import math
t = int(input())
for i in range(0, t):
	n = int(input())
	l = []
	l.insert(0, n)
	temp = int(math.ceil(n / 2))
	temp1 = n - 1
	flag = True
	while temp > 0:
		l.insert(0, temp1)
		temp = temp - 1
		temp1 = temp1 - 1
	temp1 = n + 1
	while len(l) < n:
		if temp1 > 1000000000:
			flag = False
			break
		l.append(temp1)
		temp1 = temp1 + 1
	if n == 1:
		l = [1]
	if flag:
		print(*l)
	else:
		print('-1')


t = int(input())
while t > 0:
	s = int(input())
	if s == 1:
		print('1')
	else:
		maxx = s + s // 2
		i = s // 2
		while i < maxx:
			print(i, '', end='')
			i = i + 1
		print('')
	t = t - 1


for t in range(int(input())):
	N = int(input())
	if N <= 100 and N > 1:
		for n in range(N // 2, N // 2 + N):
			print(n, end=' ')
	elif N == 1:
		print(1, end='')
	else:
		print(-1, end='')
	print()


T = int(input())
for _ in range(T):
	N = int(input())
	idx = 1
	a = [i + idx for i in range(N)]
	moy = sum(a) / len(a)
	while moy < N - 1 or moy > N + 1:
		idx += 1
		a = [i + idx for i in range(N)]
		moy = sum(a) / len(a)
	print(*a)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	if n % 2 == 0:
		L = [int(x) for x in range(n - n // 2, n + n // 2)]
	elif n == 1:
		L = [1]
	else:
		L = [int(x) for x in range(n - n // 2 - 1, n + n // 2)]
	A = [L[i:i + j] for i in range(0, n) for j in range(1, n - i + 1)]
	s = 0
	for a in A:
		c = len(a)
		if c % 2 == 0:
			median = (a[c // 2] + a[c // 2 - 1]) / 2
		else:
			median = a[c // 2]
		s = s + median
	mean = s / len(A)
	if mean >= n - 1 and mean <= n + 1:
		for ele in L:
			print(ele, end=' ')
		print()
	else:
		print(-1)


t = eval(input())
while t:
	n = eval(input())
	if n == 1:
		print(1)
	for i in range(1, n):
		sum = 0
		st = ''
		k = i
		for j in range(k, k + n):
			sum += j
			st += str(j) + ' '
		sum = sum / n
		if sum >= n - 1 and sum <= n + 1:
			print(st[0:len(st) - 1])
			break
	t -= 1


for _ in range(int(input())):
	num = int(input())
	if num == 1:
		print(1)
	elif num == 2:
		print('1 2')
	elif num == 3:
		print('1 2 3')
	else:
		sign = 1
		for i in range(num):
			print(num + sign * (1 + i // 2), end=' ')
			sign *= -1
		print()