Read problems statements in [Mandarin Chinese], [Russian], and [Bengali] as well.

Construct an array of length N containing only positive integers in the range [1, 1000] such that there doesn’t exist a subarray that has all elements occurring in even frequency and the maximum element in the array is minimized. In case there are multiple solutions, you can output any.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, one integer N. 

------ Output Format ------ 

For each test case, output in a single line N space-separated integers representing the required array. If there are multiple solutions, you may output any.

------ Constraints ------ 

$1 ≤ T ≤ 500$
$1 ≤ N ≤ 1000$

----- Sample Input 1 ------ 
3
1
2
7
----- Sample Output 1 ------ 
1
2 1
1 2 3 2 1 2 3
----- explanation 1 ------ 
Test case $1$: $[1]$ is the obvious answer.

Test case $2$: Since we need two elements and they can't be the same (otherwise the frequency of that element of the whole array is even), $[2, 1]$ is the optimal answer. $[1, 2]$ is another optimal one.

Test case $3$: It can be proven that no construction exists with the maximum element of $2$.

Difficulty: HARD
Tags: Bit manipulation

Mathematics

Constructive algorithms
Skill types: Bit manipulation

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	m = 1
	l = []
	p = 1
	s = []
	c = 0
	for j in range(n):
		if c:
			l1 = list(reversed(s))
			l += l1[0:n - len(l)]
			c = 0
			if len(l) == n:
				break
		if len(l) + 1 == 2 ** p:
			m += 1
			p += 1
			c = 1
			s = l.copy()
		l.append(m)
	l = ' '.join([str(x) for x in l])
	print(l)


for t in range(int(input())):
	n = int(input())
	maxint = 1
	l = []
	p = 1
	subseq = []
	pf = 0
	for i in range(n):
		if pf:
			t = list(reversed(subseq))
			l += t[0:n - len(l)]
			pf = 0
			if len(l) == n:
				break
		if len(l) + 1 == 2 ** p:
			maxint += 1
			p += 1
			pf = 1
			subseq = l.copy()
		l.append(maxint)
	l = ' '.join([str(e) for e in l])
	print(l)


t = int(input())
while t:
	n = int(input())
	if n == 1:
		ans = [1]
	else:
		ans = [1]
		for i in range(2, 100):
			ans += ans
			ans = ans[:len(ans) - 1]
			ans = ans + [i]
			if len(ans) >= n:
				break
	ans = ans[:n]
	for f in ans:
		print(f, end=' ')
	print()
	t -= 1


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
a = '1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 9 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 10 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 9 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4'.split(' ')
arr = [1, 2, 1]
for mx in range(3, 11):
	t = arr[:]
	arr.append(mx)
	arr.extend(t)
for _ in range(*maps()):
	(n,) = maps()
	print(*arr[:n])


import sys
import time
start_time = time.time()
try:
	sys.stdin = open('5.txt', 'r')
except:
	pass
input = sys.stdin.readline
T = int(input())
a = '1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 9 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 10 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 9 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4'.split(' ')
for _ in range(T):
	n = int(input())
	print(*a[:n])
end_time = time.time()
sys.stderr.write('Time: ' + str(end_time - start_time))


def solveG(N):
	n = len(bin(N)) - 2
	A = []
	l = 0
	for mx in range(1, n + 1):
		A.append(mx)
		l += 1
		if l == N:
			return A
		for i in range(2 ** (mx - 1) - 1):
			A.append(A[i])
			l += 1
			if l == N:
				return A
for _ in range(int(input())):
	print(*solveG(int(input())))


for tc in range(int(input())):
	n = int(input())
	dp = [[1]]
	st = 2
	for x in range(2, n + 1):
		if x % 2 == 0:
			dp.append(dp[-1] + [st])
			st += 1
		else:
			dp.append(dp[-1] + dp[-2])
		if len(dp[-1]) >= n:
			break
	for x in dp[-1][0:n]:
		print(x, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	i = 1
	p = 0
	while len(l) < n:
		l.append(i)
		for j in range(p):
			l.append(l[j])
		i += 1
		p = 2 * p + 1
	for i in range(n):
		print(l[i], end=' ')
	print()


print(*[' '.join([str(bin(i ^ i + 1).count('1')) for i in range(int(input()))]) for _ in range(int(input()))], sep='\n')


l = [1, 2, 1]
for x in range(1000):
	l.append(x + 3)
	l = l + l[:len(l) - 1]
	if len(l) > 1000:
		break
t = int(input())
while t:
	n = int(input())
	print(' '.join([str(l[x]) for x in range(n)]))
	t = t - 1


(dp, count) = ([1], 1)
while len(dp) < 1000:
	arr = dp[:]
	count += 1
	dp.append(count)
	dp.extend(arr)
for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		print(dp[i], end=' ')
	print()


dp = [1]
x = 2
while len(dp) < 1000:
	dp = dp + [x] + dp
	x += 1

def solve():
	n = int(input())
	print(*dp[:n])
for _ in range(int(input())):
	solve()


final = [1]
incr = 1
while len(final) <= 1000:
	temp = final.copy()
	incr += 1
	final.append(incr)
	final += temp

def prog_name():
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(1, 2)
	elif n == 3:
		print(1, 2, 1)
	else:
		for x in range(n):
			print(final[x], end=' ')
		print()
T = int(input())
for unique in range(T):
	prog_name()


def give(a, k):
	return a[0:-1] + [k]
a = [1, 2]
k = 3
for i in range(9):
	a += give(a, k)
	k += 1
for _ in range(int(input())):
	n = int(input())
	print(*a[0:n])


def arr(left, right, res, n, m):
	if left > right:
		return
	mid = (left + right) // 2
	res[mid] = m
	arr(left, mid - 1, res, n, m + 1)
	arr(mid + 1, right, res, n, m + 1)

def main():
	for _ in range(int(input())):
		n = int(input())
		res = [0] * n
		arr(0, n - 1, res, n, 1)
		print(*res)
main()


import sys
pow = 1
ans = [1]
for i in range(10001):
	pow = 2 * pow
	if 1001 <= pow:
		n = i
		break
x = 2
for i in range(n):
	ans = ans + [x] + ans
	x += 1
from collections import defaultdict
for _ in range(int(sys.stdin.readline())):
	n = int(input())
	for i in range(n):
		sys.stdout.write(str(ans[i]) + ' ')
	print()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
dp = [1]
x = 2
while len(dp) < 1000:
	dp = dp + [x] + dp
	x += 1

def solve():
	n = inp()
	print(*dp[:n])
for _ in range(inp()):
	solve()


ans = [0] * 1000

def solution(n):

	def recur(l, r, ele):
		nonlocal n
		if l > r:
			return
		m = (l + r) // 2
		ans[m] = ele
		recur(l, m - 1, ele + 1)
		recur(m + 1, r, ele + 1)
	recur(0, n - 1, 1)
	return ans
for _ in range(int(input())):
	n = int(input())
	print(*solution(n)[:n])


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	elif n == 2:
		print('1 2')
		continue
	elif n == 3:
		print('1 2 1')
		continue
	elif n == 4:
		print('1 2 1 3')
		continue
	lst = [0 for i in range(n + 1)]
	lst[1] = 1
	lst[2] = 2
	lst[3] = 1
	lst[4] = 3
	top = 3
	i = 5
	while i <= n:
		j = 1
		while 2 ** int(math.log(i, 2)) != i and i <= n:
			lst[i] = lst[j]
			i += 1
			j += 1
		if i > n:
			break
		lst[i] = top + 1
		top += 1
		i += 1
	print(*lst[1:])


from sys import stdin
input = stdin.readline

def answer():
	ans = [0] * n
	(skip, value) = (2, 1)
	for i in range(n):
		if ans[i] == 0:
			for j in range(i, n, skip):
				ans[j] = value
			value += 1
			skip *= 2
	return ans
for T in range(int(input())):
	n = int(input())
	print(*answer())


from sys import stdin, stdout
from collections import Counter
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))

def fn(l, r, v):
	if l > r:
		return
	mid = l + r >> 1
	ans[mid] = v
	fn(l, mid - 1, v + 1)
	fn(mid + 1, r, v + 1)
for _ in range(nmbr()):
	n = nmbr()
	ans = [0] * n
	fn(0, n - 1, 1)
	print(*ans)


t = int(input())

def lsb(num):
	idx = 0
	while num % 2 == 0:
		num = num // 2
		idx = idx + 1
	return idx + 1
while t > 0:
	n = int(input())
	ans = []
	for i in range(1, n + 1):
		ans.append(lsb(i))
	print(*ans)
	t = t - 1


t = int(input())
ans = [1]
n = 10
for i in range(2, n + 1):
	c = ans[:]
	ans.append(i)
	ans += c
for _ in range(t):
	n = int(input())
	print(*ans[:n])


s = [1]
mx = 1
while len(s) <= 1000:
	temp = s.copy()
	mx += 1
	s.append(mx)
	s.extend(temp)
for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		print(s[i], end=' ')
	print()


millors = [[1]]
for i in range(1000):
	p = millors[-1]
	for v in range(1, max(p) + 2):
		imp = {v}
		for r in p[::-1]:
			if r not in imp:
				imp.add(r)
			else:
				imp.remove(r)
				if not imp:
					break
		if imp:
			millors.append(p + [v])
			break
for _ in range(int(input())):
	n = int(input())
	print(' '.join((str(v) for v in millors[n - 1])))


t = int(input())
mylist = [1]
current = 2
while len(mylist) < 1000:
	newlist = [current]
	newlist += mylist
	mylist += newlist
	current += 1
for _ in range(t):
	n = int(input())
	for i in range(n):
		print(mylist[i], end=' ')
	print()


from collections import *
import sys
input = sys.stdin.readline

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

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
co = 3
while t:
	t -= 1
	cur = 1
	n = inp()
	have = [0 for i in range(n)]
	for i in range(1, 1000):
		fl = 0
		tu = 0
		for j in range(n):
			if have[j] == 0:
				if tu % 2 == 0:
					have[j] = i
					fl = 1
				tu += 1
		if fl == 0:
			break
	print(*have)


T = int(input())
for t in range(T):
	N = int(input())
	i = 0
	j = -1
	A = []
	curr = 1
	while i < N:
		if j == -1:
			A.append(curr)
			curr += 1
			j = i - 1
			i += 1
		else:
			A.append(A[j])
			i += 1
			j -= 1
	for a in A:
		print(a, end=' ')
	print('')


for _ in range(int(input())):
	n = int(input())
	a = [1]
	i = 2
	while len(a) < n:
		a = a + [i] + a
		i += 1
	print(*a[:n])


from sys import stdin, stdout
input = stdin.readline
pows = set()
for i in range(11):
	pows.add(1 << i)
t = int(input())
for _ in range(t):
	n = int(input())
	vals = []
	arr = []
	curr = 0
	ind = -1
	for i in range(n):
		if i + 1 in pows:
			curr += 1
			vals.append(curr)
			arr.append(curr)
			ind = -1
			continue
		ind += 1
		if ind == i:
			ind = 0
		arr.append(arr[ind])
	print(*arr)


T = int(input())
for test in range(T):
	N = int(input())
	if N == 1:
		print(1)
		continue
	elif N == 2:
		print(1, 2)
		continue
	res = [1]
	N -= 1
	l = 0
	max_el = 2
	while N > 0:
		res.append(max_el)
		N -= 1
		r = len(res) - 1
		max_el += 1
		l = 0
		while l < r and N > 0:
			res.append(res[l])
			l += 1
			N -= 1
	print(' '.join([str(x) for x in res]))


def construct(N):
	arr = []
	top = 1
	while len(arr) < N:
		arr = arr + [top] + arr
		top += 1
	return arr
A = [str(x) for x in construct(1000)]
T = int(input())
for t in range(T):
	N = int(input())
	print(' '.join(A[:N]))


import bisect
s = ['1']
PRESEQ = []
PRESEQL = []
while len(s) <= 1000:
	PRESEQ.append(s)
	PRESEQL.append(len(s))
	s = s + [str(len(PRESEQ) + 1)] + s
PRESEQ.append(s)
PRESEQL.append(len(s))
for _ in range(int(input())):
	n = int(input())
	b = bisect.bisect_left(PRESEQL, n)
	p = PRESEQ[b]
	print(' '.join(p[:n]))