You have a sequence of $n$ colored blocks. The color of the $i$-th block is $c_i$, an integer between $1$ and $n$.

You will place the blocks down in sequence on an infinite coordinate grid in the following way.

Initially, you place block $1$ at $(0, 0)$.

For $2 \le i \le n$, if the $(i - 1)$-th block is placed at position $(x, y)$, then the $i$-th block can be placed at one of positions $(x + 1, y)$, $(x - 1, y)$, $(x, y + 1)$ (but not at position $(x, y - 1)$), as long no previous block was placed at that position.

A tower is formed by $s$ blocks such that they are placed at positions $(x, y), (x, y + 1), \ldots, (x, y + s - 1)$ for some position $(x, y)$ and integer $s$. The size of the tower is $s$, the number of blocks in it. A tower of color $r$ is a tower such that all blocks in it have the color $r$.

For each color $r$ from $1$ to $n$, solve the following problem independently:

Find the maximum size of a tower of color $r$ that you can form by placing down the blocks according to the rules.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output $n$ integers. The $r$-th of them should be the maximum size of an tower of color $r$ you can form by following the given rules. If you cannot form any tower of color $r$, the $r$-th integer should be $0$.


-----Examples-----

Input
6
7
1 2 3 1 2 3 1
6
4 2 2 2 4 4
1
1
5
5 4 5 3 5
6
3 3 3 1 3 3
8
1 2 3 4 4 3 2 1
Output
3 2 2 0 0 0 0 
0 3 0 2 0 0 
1 
0 0 1 1 1 
1 0 4 0 0 0 
2 2 2 2 0 0 0 0


-----Note-----

In the first test case, one of the possible ways to form a tower of color $1$ and size $3$ is:

place block $1$ at position $(0, 0)$;

place block $2$ to the right of block $1$, at position $(1, 0)$;

place block $3$ above block $2$, at position $(1, 1)$;

place block $4$ to the left of block $3$, at position $(0, 1)$;

place block $5$ to the left of block $4$, at position $(-1, 1)$;

place block $6$ above block $5$, at position $(-1, 2)$;

place block $7$ to the right of block $6$, at position $(0, 2)$.

The blocks at positions $(0, 0)$, $(0, 1)$, and $(0, 2)$ all have color $1$, forming an tower of size $3$.

In the second test case, note that the following placement is not valid, since you are not allowed to place block $6$ under block $5$:

It can be shown that it is impossible to form a tower of color $4$ and size $3$.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Mathematics

Greedy algorithms


Solutions:
import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	tmp = sys.stdin.readline().split(' ')
	c = list(map(int, tmp))
	ans = [0 for j in range(n)]
	prev = [-1 for j in range(n)]
	for j in range(len(c)):
		if prev[c[j] - 1] == -1:
			prev[c[j] - 1] = j
			ans[c[j] - 1] += 1
		elif (j - prev[c[j] - 1]) % 2 == 1:
			prev[c[j] - 1] = j
			ans[c[j] - 1] += 1
	ans = list(map(str, ans))
	print(' '.join(ans))


t = int(input())
for i in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	result = [0] * n
	meta = [-1] * (n + 1)
	for (index, num) in enumerate(nums):
		last_index = meta[num]
		if last_index == -1:
			result[num - 1] = 1
			meta[num] = index
		elif index % 2 != last_index % 2:
			result[num - 1] += 1
			meta[num] = index
	print(' '.join([str(r) for r in result]))


for _ in range(int(input())):
	n = int(input())
	count = [0] * n
	last = [None] * n
	c = [int(x) - 1 for x in input().split()]
	for (i, x) in enumerate(c):
		if last[x] is None:
			last[x] = i % 2
			count[x] = 1
			continue
		if last[x] != i % 2:
			last[x] = 1 - last[x]
			count[x] += 1
	print(' '.join(map(str, count)))


t = int(input())

def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	ans = [0] * n
	hash_map = {}
	for i in range(len(lst)):
		if not lst[i] in hash_map:
			hash_map[lst[i]] = i
			ans[lst[i] - 1] = 1
		elif (i - hash_map[lst[i]]) % 2 != 0:
			ans[lst[i] - 1] += 1
			hash_map[lst[i]] = i
	print(' '.join((str(ele) for ele in ans)))
while t:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	l = [0 for _ in range(n)]
	prev = [0 for _ in range(n)]
	for i in range(1, n + 1):
		if prev[c[i - 1] - 1] == 0 or (i - prev[c[i - 1] - 1]) % 2 != 0:
			l[c[i - 1] - 1] += 1
			prev[c[i - 1] - 1] = i
	print(' '.join(map(str, l)))


for _ in range(int(input())):
	n = int(input())
	c = tuple(map(int, input().split()))
	ans = [0] * n
	d = {}
	for i in range(n):
		r = c[i]
		if r not in d:
			ans[r - 1] += 1
		elif i - d[r] == 1:
			ans[r - 1] += 1
		elif (i - d[r]) % 2 == 1:
			ans[r - 1] += 1
		d[r] = i
	print(' '.join((str(i) for i in ans)))


def validate(arr):
	count_vector = [0 for _ in range(len(arr))]
	indexes = [-1 for _ in range(len(arr))]
	for i in range(len(arr)):
		if indexes[arr[i] - 1] == -1:
			indexes[arr[i] - 1] = i
			count_vector[arr[i] - 1] += 1
		elif (i - indexes[arr[i] - 1]) % 2:
			indexes[arr[i] - 1] = i
			count_vector[arr[i] - 1] += 1
	return ' '.join([str(x) for x in count_vector])
t = int(input())
for _ in range(t):
	n = int(input())
	colors = [int(x) for x in input().split()]
	print(validate(colors))


t = int(input())
for i in range(t):
	l = input()
	l1 = list(map(int, input().split()))
	n = int(l)
	ans = {}
	for i in range(1, n + 1):
		ans[i] = 0
	prev_idx = {}
	for i in range(n):
		if ans[l1[i]] == 0:
			ans[l1[i]] = 1
			prev_idx[l1[i]] = i
		else:
			if (i - prev_idx[l1[i]]) % 2 == 1:
				ans[l1[i]] += 1
			prev_idx[l1[i]] = i
	res = ' '.join([str(e) for e in ans.values()])
	print(res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans0 = [[] for i in range(n + 1)]
	for (i, x) in enumerate(a):
		if len(ans0[x]) == 0:
			ans0[x].append(i)
		elif ans0[x][-1] % 2 != i % 2:
			ans0[x].append(i)
	ans = []
	for i in range(1, n + 1):
		ans.append(len(ans0[i]))
	print(' '.join(map(str, ans)))


t = int(input())
for _ in range(t):
	last_seen = {}
	count = {}
	n = int(input())
	a = list(map(int, input().split(' ')))
	for (i, color) in enumerate(a):
		if color not in last_seen:
			count[color] = 1
			last_seen[color] = i
		elif (i - last_seen[color]) % 2 == 1:
			count[color] += 1
			last_seen[color] = i
	ans = []
	for i in range(1, n + 1):
		if i in count:
			ans.append(count[i])
		else:
			ans.append(0)
	print(' '.join([str(b) for b in ans]))


t = int(input())
ans = list()
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	t = n * [0]
	p = n * [-1]
	for i in range(0, n):
		if t[arr[i] - 1] == 0:
			t[arr[i] - 1] = 1
		if p[arr[i] - 1] != -1 and (p[arr[i] - 1] - i) % 2 == 1:
			t[arr[i] - 1] += 1
		p[arr[i] - 1] = i
	s = ''
	for x in t:
		s += f'{x} '
	ans.append(s)
for s in ans:
	print(s)


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	d = dict()
	ans = [0 for i in range(n)]
	for i in range(n):
		if l[i] in d:
			d[l[i]].append(i)
		else:
			d[l[i]] = [i]
	for i in d.keys():
		c = 0
		start = d[i][0] % 2
		for j in range(1, len(d[i])):
			if d[i][j] % 2 == (start + 1) % 2:
				c += 1
				start = (start + 1) % 2
		ans[i - 1] = c + 1
	print(' '.join(map(str, ans)))
t = int(input())
while t > 0:
	solve()
	t -= 1


def solveonecolor(array):
	m = len(array)
	if m == 0:
		return 0
	elif m == 1:
		return 1
	else:
		maxi = 1
		for i in range(m - 1):
			if (array[i + 1] - array[i]) % 2 == 1:
				maxi += 1
	return maxi

def solve(n, array):
	allans = []
	subarrays = [[] for _ in range(n)]
	for i in range(n):
		color = array[i] - 1
		subarrays[color].append(i)
	for color in range(n):
		allans.append(solveonecolor(subarrays[color]))
	print(' '.join((str(i) for i in allans)))
tests = int(input())
for _ in range(tests):
	n = int(input())
	array = list(map(int, input().split()))
	solve(n, array)


t = int(input())
for _ in range(0, t):
	n = int(input())
	c = list((int(s) for s in input().split()))
	c.insert(0, None)
	started = [False] * (n + 1)
	isEven = [None] * (n + 1)
	count = [0] * (n + 1)
	for i in range(1, n + 1):
		if count[c[i]] == 0:
			isEven[c[i]] = i % 2 == 0
			count[c[i]] = 1
		elif isEven[c[i]] and i % 2 != 0:
			isEven[c[i]] = False
			count[c[i]] += 1
		elif not isEven[c[i]] and i % 2 == 0:
			isEven[c[i]] = True
			count[c[i]] += 1
	out = []
	for i in range(1, n + 1):
		out.append(str(count[i]))
		out.append(' ')
	print(''.join(out[:-1]))


def solution(n, arr):
	res = []
	dic = {}
	for i in range(len(arr)):
		dic[arr[i]] = dic.get(arr[i], [])
		dic[arr[i]].append(i)
	for i in range(1, n + 1):
		if dic.get(i, 0) == 0:
			res.append('0')
		else:
			s = 1
			current = dic[i][0]
			if len(dic[i]) > 1:
				for j in range(1, len(dic[i])):
					if (dic[i][j] - current - 1) % 2 == 0:
						s += 1
						current = dic[i][j]
			res.append(str(s))
	return ' '.join(res)
N = int(input())
for _ in range(N):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	print(solution(n, arr))


trails = int(input())
for x in range(trails):
	n = int(input())
	k = input().split(' ')
	ans = [0] * n
	li = [-1] * n
	index = -1
	for p in k:
		index += 1
		g = int(p)
		li_val = li[g - 1]
		if (index - li_val) % 2 == 1 or li_val == -1:
			ans[g - 1] = ans[g - 1] + 1
		li[g - 1] = index
	ans_str = ''
	for i in ans:
		ans_str += str(i)
		ans_str += ' '
	print(ans_str)


import collections
for _ in range(int(input())):
	n = int(input())
	nums = input().split(' ')
	di = collections.defaultdict(list)
	colors = [0] * (n + 1)
	for i in range(n):
		di[nums[i]].append(i)
	for i in di:
		count = 1
		k = di[i]
		for j in range(len(k) - 1):
			if (k[j + 1] - k[j]) % 2 == 1:
				count += 1
		colors[int(i)] = count
	colors.pop(0)
	print(' '.join(list(map(str, colors))))


for _ in range(int(input())):
	n = int(input())
	arr = input().split()
	dp = {}
	result = [0] * n
	for i in range(n):
		if arr[i] not in dp:
			dp[arr[i]] = [i]
		else:
			dp[arr[i]].append(i)
	for i in dp:
		arr1 = dp[i]
		count = 1
		n1 = len(arr1)
		for j in range(1, n1):
			if arr1[j] - arr1[j - 1] == 1 or (arr1[j] - arr1[j - 1]) % 2 == 1:
				count += 1
			else:
				continue
		result[int(i) - 1] = count
	print(' '.join(map(str, result)))


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	last = [-1] * (n + 1)
	final = [0] * (n + 1)
	for i in range(n):
		curr = arr[i]
		if final[curr] == 0:
			final[curr] = 1
			last[curr] = i
		elif (i - last[curr]) % 2:
			last[curr] = i
			final[curr] += 1
	for z in final[1:]:
		print(z, end=' ')
	print()
	return
for _ in range(int(input())):
	main()


from collections import defaultdict

def sol(arr):
	dic = defaultdict(list)
	for i in range(len(arr)):
		dic[arr[i]].append(i)
	ans = [0 for _ in range(len(arr))]
	for key in dic:
		dic[key] = sorted(dic[key])
		if len(dic[key]) == 0:
			ans[key - 1] = 0
			continue
		elif len(dic[key]) == 1:
			ans[key - 1] = 1
			continue
		count = 1
		for i in range(1, len(dic[key])):
			if (dic[key][i] - dic[key][i - 1]) % 2 != 0:
				count += 1
		ans[key - 1] = count
	return ' '.join(map(str, ans))
x = int(input())
for _ in range(x):
	n = int(input())
	arr = list(map(int, input().split()))
	print(sol(arr))


t = int(input())
for jj in range(t):
	n = int(input())
	p = [int(i) for i in input().split(' ')]
	dic = {}
	for (i, v) in enumerate(p):
		if v not in dic:
			dic[v] = [i]
		else:
			dic[v].append(i)
	ans = []

	def cal(a):
		if len(a) == 1:
			return 1
		res = 1
		tag = a[0] % 2
		for i in range(1, len(a)):
			if a[i] % 2 != tag:
				tag = (tag + 1) % 2
				res += 1
		return res
	for i in range(1, n + 1):
		if i not in dic:
			ans.append(0)
		else:
			ans.append(cal(dic[i]))
	k = [str(i) for i in ans]
	print(' '.join(k))


for _ in range(int(input())):
	n = int(input())
	c = [int(x) - 1 for x in input().split()]
	towers = [[0, 0] for _ in c]
	for i in range(n - 1, -1, -1):
		parity = i % 2
		towers[c[i]][parity] = 1 + towers[c[i]][int(not parity)]
	print(' '.join([str(max(x)) for x in towers]))


import sys, math

def get_line_ints(stream):
	return [int(x) for x in next(lines).rstrip().split(' ')]
lines = sys.stdin
n_cases = get_line_ints(lines)[0]
for case_ndx in range(n_cases):
	n = get_line_ints(lines)[0]
	col_ints = get_line_ints(lines)
	max_towers = []
	col_indices_list = []
	for _ in range(n):
		col_indices_list.append([])
	for (i, col) in enumerate(col_ints):
		col_indices_list[col - 1].append(i % 2)
	for col_ndx in range(n):
		col_indices = col_indices_list[col_ndx]
		if len(col_indices) == 0:
			max_towers.append(0)
			continue
		tower_count = 1
		parity = col_indices[0]
		for current_parity in col_indices[1:]:
			if current_parity != parity:
				parity = current_parity
				tower_count += 1
		max_towers.append(tower_count)
	print(' '.join([str(x) for x in max_towers]))


t = int(input())
for _ in range(t):
	n = int(input())
	c = [int(x) for x in input().split()]
	C = set(c)
	sol = [0 for _ in range(n)]
	runs = dict()
	for (i, x) in enumerate(c):
		if x not in runs:
			runs[x] = [1, i]
		else:
			(a, b) = runs[x]
			if (i - b) % 2:
				runs[x] = [a + 1, i]
	for i in range(n):
		if i + 1 in C:
			sol[i] = runs[i + 1][0]
	print(' '.join((str(x) for x in sol)))


for _ in range(int(input())):
	n = int(input())
	last = [None] * n
	count = [0] * n
	for (i, x) in enumerate(input().split()):
		x = int(x) - 1
		if last[x] is None or (last[x] + i) % 2 == 1:
			last[x] = i
			count[x] += 1
	print(*count)


for qwerty in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [0] * n + [0]
	ans = ''
	for (j, i) in enumerate(l):
		if l1[i] == 0:
			l1[i] = [j % 2]
			continue
		l1[i] += [j % 2]
	for i in range(1, n + 1):
		t = l1[i]
		if t == 0:
			ans += '0 '
		else:
			ans1 = 1
			x = t[0]
			for i in t:
				if x == 0:
					if i == 1:
						ans1 += 1
						x = 1
				elif i == 0:
					ans1 += 1
					x = 0
			ans += str(ans1) + ' '
	print(ans)


test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = [0] * (n + 1)
	towers = dict()
	for (i, j) in enumerate(a):
		if j in towers:
			if towers[j] % 2 != i % 2:
				towers[j] = i % 2
				ans[j] += 1
		else:
			towers[j] = i % 2
			ans[j] += 1
	print(*ans[1:])
	test -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	c = list(map(int, input().split()))
	marker = [[] for i in range(n + 1)]
	for i in range(n):
		marker[c[i]].append(i)
	ans = []
	for i in range(1, n + 1):
		if len(marker[i]) == 0:
			ans.append(str(0))
		else:
			M = 1
			for j in range(1, len(marker[i])):
				if (marker[i][j] - marker[i][j - 1]) % 2 == 1:
					M += 1
			ans.append(str(M))
	print(' '.join(ans))


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	stack = [0, 0] * n
	a = [int(x) for x in input().split()]
	for i in range(0, n):
		if stack[a[i] + n - 1] == 0 and stack[a[i] - 1] == 0:
			stack[a[i] + n - 1] = i
			stack[a[i] - 1] += 1
		else:
			x = i - stack[a[i] + n - 1]
			if x % 2 == 1:
				stack[a[i] - 1] += 1
				stack[a[i] + n - 1] = i
	stack2 = []
	for i in range(0, n):
		stack2.append(str(stack[i]))
	print(' '.join(stack2))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = [0] * (n + 1)
	ind = [-1] * (n + 1)
	for i in range(n):
		if ind[l[i]] == -1 or (i - ind[l[i]]) % 2:
			ans[l[i]] += 1
		ind[l[i]] = i
	print(*ans[1:n + 1])


from re import A
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	d = [0] * n
	e = [-1] * n
	for i in range(n):
		if e[c[i] - 1] != -1:
			if (i - e[c[i] - 1]) % 2 == 1:
				d[c[i] - 1] += 1
				e[c[i] - 1] = i
		else:
			d[c[i] - 1] = 1
			e[c[i] - 1] = i
	print(*d)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * n
	p = [0] * n
	for (i, c) in enumerate(a):
		if ans[c - 1] == 0:
			ans[c - 1] += 1
			p[c - 1] = i
		elif (i - p[c - 1]) % 2 == 1:
			ans[c - 1] += 1
			p[c - 1] = i
	print(*ans)


t = int(input())
for i in range(t):
	m = int(input())
	arr = list(map(int, input().strip().split()))[:m]
	prev = [-1] * (m + 1)
	brr = [0] * (m + 1)
	for j in range(m):
		if prev[arr[j]] == -1:
			prev[arr[j]] = j + 1
			brr[arr[j]] = 1
		elif (j + 1 - prev[arr[j]]) % 2 != 0:
			brr[arr[j]] += 1
			prev[arr[j]] = j + 1
	crr = brr[1:]
	print(*crr)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [j - 1 for j in arr]
	ans = [0] * n
	ps = [-1] * n
	for j in range(n):
		if ps[arr[j]] == -1:
			ps[arr[j]] = j
			ans[arr[j]] = 1
		elif (j - ps[arr[j]]) % 2:
			ps[arr[j]] = j
			ans[arr[j]] += 1
	print(*ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = [[] for _ in range(n + 1)]
	for i in range(n):
		if not cnt[arr[i]]:
			cnt[arr[i]].append(i)
		elif (i - cnt[arr[i]][-1]) % 2:
			cnt[arr[i]].append(i)
	ans = [0] * (n + 1)
	for i in range(n + 1):
		ans[i] = len(cnt[i])
	return ans[1:]
for _ in range(int(input())):
	print(*solve())


for _ in range(int(input())):
	n = int(input())
	mass = list(map(int, input().split()))
	f = {}
	for i in range(n):
		if mass[i] not in f:
			f[mass[i]] = []
		f[mass[i]].append(i)
	s = ''
	for i in range(1, n + 1):
		if i not in f:
			s += '0 '
		else:
			w = f[i]
			k = 1
			otv = 1
			if len(w) > 1:
				for j in range(1, len(w)):
					if (w[j] - w[j - 1] - 1) % 2 == 0:
						k += 1
					otv = max(otv, k)
			s += f'{otv} '
	print(s)


t = int(input())
while t:
	n = int(input())
	s = input().split()
	c = list(map(int, s))
	d = {}
	for i in range(n):
		d[i + 1] = []
	for i in range(n):
		d[c[i]].append(i)
	ans = []
	for i in range(1, n + 1):
		if len(d[i]) == 0:
			ans.append(0)
			continue
		val = 1
		for j in range(1, len(d[i])):
			if (d[i][j] - d[i][j - 1]) % 2 != 0:
				val += 1
		ans.append(val)
	print(' '.join(map(str, ans)))
	t -= 1


standard_input = '6\n7\n1 2 3 1 2 3 1\n6\n4 2 2 2 4 4\n1\n1\n5\n5 4 5 3 5\n6\n3 3 3 1 3 3\n8\n1 2 3 4 4 3 2 1\n'

def trySeq(space):
	total = 0
	bestEvenCount = 1
	bestOddCount = 0
	for i in range(len(space)):
		v = space[i]
		total += v
		even = total % 2 == 0
		if even:
			bestEvenCount = max(bestEvenCount, bestOddCount + 1)
		else:
			bestOddCount = max(bestOddCount, bestEvenCount + 1)
	return max(bestEvenCount, bestOddCount)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prev = [-1 for _ in range(n)]
	spacings = [[] for _ in range(n)]
	for i in range(n):
		v = a[i] - 1
		if prev[v] != -1:
			spacings[v].append(i - prev[v])
		prev[v] = i
	arr = []
	for i in range(n):
		if prev[i] == -1:
			arr.append(0)
		else:
			arr.append(trySeq(spacings[i]))
	print(' '.join(map(str, arr)))


t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	M = [0] * n
	N = [-1] * n
	for i in range(n):
		a = L[i]
		if M[a - 1] == 0:
			M[a - 1] += 1
			N[a - 1] = i % 2
		elif i % 2 == N[a - 1]:
			pass
		else:
			N[a - 1] = i % 2
			M[a - 1] += 1
	print(*M)


from typing import List
from collections import defaultdict

class Solution:

	def solve(self, n, c):
		ans = ['0'] * (n + 1)
		ht = defaultdict(list)
		for (i, color) in enumerate(c):
			ht[color].append(i)
		for (color, arr) in ht.items():
			ans[color] = str(1)
			(odd, even) = (0, 0)
			for ind in arr:
				if ind % 2 == 0:
					even = max(odd + 1, even)
				else:
					odd = max(even + 1, odd)
			ans[color] = str(max(even, odd))
		return ' '.join(ans[1:])
obj = Solution()
T = int(input())
for _ in range(T):
	n = int(input())
	c = list(map(int, input().split()))
	ans = obj.solve(n, c)
	print(ans)


test = int(input())

def value(array, n):
	hmap = {}
	for i in range(n):
		if array[i] not in hmap:
			hmap[array[i]] = [i]
		else:
			hmap[array[i]].append(i)
	result = [0 for i in range(n)]
	for i in range(n):
		if i + 1 in hmap:
			indices = hmap[i + 1]
			oddCount = 0
			evenCount = 0
			odd = True
			even = True
			for index in indices:
				if odd and index % 2 == 1:
					oddCount += 1
					odd = False
				elif not odd and index % 2 == 0:
					oddCount += 1
					odd = True
				if even and index % 2 == 0:
					evenCount += 1
					even = False
				elif not even and index % 2 == 1:
					evenCount += 1
					even = True
			result[i] = max(evenCount, oddCount)
	answer = []
	for num in result:
		answer.append(str(num))
		answer.append(' ')
	return ''.join(answer)
for i in range(test):
	n = int(input())
	array = list(map(int, input().split()))
	print(value(array, n))


for _ in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split()))
	result = [0] * n
	r_last_index = [-1] * n
	for i in range(n):
		r = numbers[i] - 1
		if r_last_index[r] == -1 or (i - r_last_index[r]) % 2 == 1:
			r_last_index[r] = i
			result[r] += 1
	print(*result, sep=' ')


for t in range(int(input())):
	n = int(input())
	ar = [*map(int, input().split())]
	l = [0] * n
	prev = [0] * n
	for i in range(1, n + 1):
		if prev[ar[i - 1] - 1] == 0 or (i - prev[ar[i - 1] - 1]) % 2 != 0:
			prev[ar[i - 1] - 1] = i
			l[ar[i - 1] - 1] += 1
	print(*l)


for s in [*open(0)][2::2]:
	a = s.split()
	r = [[0, 0] for _ in a]
	i = 0
	for x in a:
		x = int(x) - 1
		r[x][i & 1] = r[x][~i & 1] + 1
		i += 1
	print(*map(max, r))


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	a = [-1] * (n + 1)
	res = [0] * (n + 1)
	for i in range(1, n + 1):
		if a[arr[i]] == -1:
			a[arr[i]] = i % 2
			res[arr[i]] = res[arr[i]] + 1
		elif a[arr[i]] != i % 2:
			a[arr[i]] = i % 2
			res[arr[i]] = res[arr[i]] + 1
	res.pop(0)
	print(*res)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0 for i in range(n)]
	d = {}
	for i in range(len(arr)):
		if arr[i] not in d:
			d[arr[i]] = i
			ans[arr[i] - 1] += 1
		else:
			diff = abs(d[arr[i]] - i) - 1
			if diff % 2 == 0:
				ans[arr[i] - 1] += 1
				d[arr[i]] = i
	print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		arr[i] = arr[i] - 1
	sign = [0 for i in range(n)]
	ind = [0 for i in range(n)]
	cnt = [0 for i in range(n)]
	for i in range(n):
		if sign[arr[i]] == 0:
			sign[arr[i]] = 1
			ind[arr[i]] = i
			cnt[arr[i]] = 1
		else:
			if (ind[arr[i]] - i) % 2 == 1:
				cnt[arr[i]] += 1
			ind[arr[i]] = i
	s = ''
	for i in range(n):
		s += str(cnt[i]) + ' '
	print(s)


T = int(input())
for test in range(T):
	N = int(input())
	Color = list(map(int, input().split()))
	Answer = [0] * (N + 1)
	dict_val = {}
	for (index, i) in enumerate(Color):
		if i not in dict_val:
			Answer[i] += 1
			dict_val[i] = index
		elif (index - dict_val[i] - 1) % 2 == 0:
			Answer[i] += 1
			dict_val[i] = index
	for i in range(1, N):
		print(Answer[i], end=' ')
	print(Answer[N])


def miis():
	return map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	a = list(miis())
	ans = [0 for i in range(n + 1)]
	last = [-1 for i in range(n + 1)]
	for i in range(n):
		if ans[a[i]] == 0:
			ans[a[i]] = 1
		elif (i - last[a[i]]) % 2 or i - last[a[i]] == 1:
			ans[a[i]] += 1
		last[a[i]] = i
	print(*ans[1:])


def func():
	n = int(input())
	arr = list(map(int, input().split()))
	a = [0] + arr + [0]
	mp = {}
	for i in range(1, n + 1):
		if a[i] not in mp:
			mp[a[i]] = [i]
		else:
			mp[a[i]].append(i)
	tmp = [0] * (n + 2)
	for key in mp:
		count = 1
		for i in range(1, len(mp[key])):
			if mp[key][i] - mp[key][i - 1] - 1 & 1:
				continue
			count += 1
		tmp[key] = count
	print(*tmp[1:n + 1])
tc = int(input())
while tc > 0:
	func()
	tc -= 1


for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	ans = [0] * n
	d = {}
	for i in range(0, n):
		c = s[i]
		if c in d.keys():
			if (i - d[c][0][1]) % 2 == 1:
				d[c][0][0] += 1
				d[c][0][1] = i
			elif d[c][1][0] == 0:
				d[c][1][0] += 1
				d[c][1][1] = i
			elif (i - d[c][1][1]) % 2 == 1:
				d[c][1][0] += 1
				d[c][1][1] = i
		else:
			d[c] = [[1, i], [0, 0]]
	for i in d.keys():
		ans[i - 1] = max(d[i][0][0], d[i][1][0])
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	n = int(input())
	seq = list(map(int, input().split()))
	res = [0 for _ in range(n)]
	last = {}
	for i in range(n):
		if seq[i] not in last:
			res[seq[i] - 1] = 1
		res[seq[i] - 1] += (i - last.get(seq[i], i)) % 2
		last[seq[i]] = i
	print(*res)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	dic = {}
	ans = [0] * (n + 1)
	for i in range(len(lst)):
		if lst[i] in dic:
			if i % 2 != dic[lst[i]]:
				ans[lst[i]] += 1
				dic[lst[i]] = i % 2
		else:
			dic[lst[i]] = i % 2
			ans[lst[i]] = 1
	for i in ans[1:]:
		print(i, end=' ')
	print()


for s in [*open(0)][2::2]:
	ajo = s.split()
	min = [[0, 0] for _ in ajo]
	i = 0
	for jx in ajo:
		jx = int(jx) - 1
		min[jx][i & 1] = min[jx][~i & 1] + 1
		i += 1
	print(*map(max, min))


t = int(input())
for i in range(t):
	n = int(input())
	nums = [int(temp) for temp in input().split()]
	first = [-1] * (n + 1)
	odds = [0] * (n + 1)
	for i in range(n):
		x = nums[i]
		if first[x] == -1:
			odds[x] += 1
			first[x] = i
		elif (i - first[x] - 1) % 2 == 0:
			odds[x] += 1
			first[x] = i
	for i in range(1, n + 1):
		print(odds[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	d = {}
	for (i, ci) in enumerate((*map(int, input().split()),)):
		if ci not in d:
			d[ci] = [i]
		elif i & 1 != d[ci][-1] & 1:
			d[ci].append(i)
	print(*(len(d.get(ci, [])) for ci in range(1, n + 1)))


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if d.get(c[i], None) is None:
			d[c[i]] = [1, i % 2]
		elif d[c[i]][1] != i % 2:
			d[c[i]][0] += 1
			d[c[i]][1] ^= 1
	print(*(d.get(i, [0])[0] for i in range(1, n + 1)))


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = [[] for o in range(n)]
	for r in range(n):
		d[a[r] - 1] += [r]
	ans = [0] * n
	for i in range(n):
		if len(d[i]) != 0:
			ans[i] = 1
		for j in range(1, len(d[i])):
			if d[i][j] - d[i][j - 1] - 1 & 1 == 0:
				ans[i] += 1
	print(' '.join(map(str, ans)))


import sys
printf = sys.stdout.write

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

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

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

def get_liss():
	return sys.stdin.readline().split()

def get_ints():
	return sys.stdin.readline().split()

def get_str():
	return sys.stdin.readline().strip()

def pop_zeros(items):
	while items[-1] == 0:
		items.pop()
from collections import defaultdict
import math
t = intput()
while t:
	n = intput()
	l = get_lis()
	dic = {}
	dicc = {}
	for i in range(n):
		if l[i] not in dic:
			dic[l[i]] = [i]
			dicc[l[i]] = [i]
		else:
			dicc[l[i]].append(i)
			dic[l[i]].append(i - dicc[l[i]][-2])
	lans = [0] * n
	for ele in dic.keys():
		if len(dic[ele]) >= 1:
			ans = 1
			for i in range(1, len(dic[ele])):
				if dic[ele][i] % 2 != 0:
					ans += 1
			lans[ele - 1] = ans
	printf(' '.join((str(x) for x in lans)))
	printf('\n')
	t -= 1


T = int(input())
for t in range(T):
	n = int(input())
	arr = input().split()
	arr = list(map(int, arr))
	(x, y) = (0, 0)
	ans = [0] * n
	ind = [-1] * n
	p = arr[0] - 1
	ans[p] = 1
	ind[p] = 0
	for i in range(1, n):
		p = arr[i] - 1
		if ind[p] == -1:
			ans[p] = 1
			ind[p] = i
		elif i - ind[p] == 1 or (i - ind[p]) % 2 != 0:
			ans[p] += 1
		ind[p] = i
	for i in ans:
		print(i, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	size = [0] * n
	mydict = {}
	for i in range(n):
		if a[i] not in mydict:
			size[a[i] - 1] += 1
			mydict[a[i]] = i
		elif (i - mydict[a[i]] + 1) % 2 == 0:
			size[a[i] - 1] += 1
			mydict[a[i]] = i
	for s in size:
		print(s, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = []
	mod = []
	for i in range(n):
		ans.append(0)
		mod.append(-1)
	for i in range(n):
		ans[l[i] - 1] = 1
	for i in range(n):
		if mod[l[i] - 1] == -1:
			mod[l[i] - 1] = i % 2
		elif mod[l[i] - 1] != i % 2:
			ans[l[i] - 1] += 1
			mod[l[i] - 1] = i % 2
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	ans = [[0, '0'] for _ in range(n)]
	for (index, value) in enumerate(map(int, input().split())):
		a = index % 2
		if a != ans[value - 1][1]:
			ans[value - 1][0] += 1
			ans[value - 1][1] = a
	print(*map(lambda x: x[0], ans))


import sys
input = sys.stdin.readline
from collections import defaultdict
t = int(input())
for _ in range(t):
	saveIdx = defaultdict(list)
	n = int(input())
	order = list(map(int, input().split()))
	answer = [0] * (n + 1)
	for i in range(n):
		if order[i] in saveIdx:
			if (i + 1 - saveIdx[order[i]][0]) % 2 == 1:
				saveIdx[order[i]][0] = i + 1
				saveIdx[order[i]][1] += 1
		else:
			saveIdx[order[i]] = [i + 1, 1]
	for key in saveIdx.keys():
		answer[key] = saveIdx[key][1]
	for j in range(1, len(answer)):
		print(answer[j], end=' ')
	print()


def solve():
	n = int(input())
	lst = list(map(int, input().split(' ')))
	dct = {}
	ans = [0] * n
	for i in range(n):
		if lst[i] in dct:
			dct[lst[i]].append(i)
		else:
			dct[lst[i]] = [i]
	for i in dct:
		cnt = 1
		for j in range(len(dct[i]) - 1):
			if (dct[i][j + 1] - dct[i][j]) % 2:
				cnt += 1
		ans[i - 1] = cnt
	for i in ans:
		print(i, end=' ')
	print()
t = int(input())
while t:
	t -= 1
	solve()


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	list2 = [0 for i in range(0, n)]
	list2[list1[0] - 1] += 1
	last_ind = [0 for i in range(0, n)]
	for i in range(1, n):
		if list2[list1[i] - 1] == 0:
			list2[list1[i] - 1] += 1
			last_ind[list1[i] - 1] = i
		elif list1[i] == list1[i - 1]:
			list2[list1[i] - 1] += 1
			last_ind[list1[i] - 1] = i
		else:
			diff = i - last_ind[list1[i] - 1]
			if i - 2 < 0:
				list2[list1[i] - 1] += 1
				last_ind[list1[i] - 1] = i
			elif diff % 2 == 1:
				list2[list1[i] - 1] += 1
				last_ind[list1[i] - 1] = i
	print(*list2)


import sys
inp = sys.stdin.readline
for _ in range(int(inp())):
	n = int(inp())
	c = list(map(int, inp().split()))
	res = {}
	for i in range(n):
		try:
			res[c[i]]
			if (i - res[c[i]][0] - 1) % 2 == 0:
				res[c[i]][1] += 1
			res[c[i]][0] = i
		except Exception:
			res[c[i]] = [i, 1]
	for i in range(1, n + 1):
		if i in res:
			print(res[i][1], end=' ')
		else:
			print(0, end=' ')
	print()


for sasuke in [*open(0)][2::2]:
	asta = sasuke.split()
	rimuru = [[0, 0] for jiraya in asta]
	itadori = 0
	for xeno in asta:
		xeno = int(xeno) - 1
		rimuru[xeno][itadori & 1] = rimuru[xeno][~itadori & 1] + 1
		itadori += 1
	print(*map(max, rimuru))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	maxi = [0] * (n + 1)
	if 3434 == 'dfdjfhgrh':
		print('Tanmay')
	prev = [0] * (n + 1)
	c = [0] * (n + 1)
	for i in range(1, n + 1):
		x = a[i - 1]
		if prev[x] == 0:
			c[x] += 1
			maxi[x] += 1
			prev[x] = i
			continue
		if (i - prev[x]) % 2 == 1:
			c[x] += 1
			maxi[x] = max(c[x], maxi[x])
			prev[x] = i
	for i in maxi[1:]:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	res = [0 for _ in range(n)]
	info = {}
	for i in range(n):
		if c[i] not in info:
			res[c[i] - 1] = 1
		res[c[i] - 1] += (i - info.get(c[i], i)) % 2
		info[c[i]] = i
	print(*res)


def main():
	for t in range(int(input())):
		n = int(input())
		c = [0] + list(map(int, input().split()))
		ans = [[] for i in range(n + 1)]
		pre = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			if pre[c[i]] == 0:
				ans[c[i]].append(1)
				pre[c[i]] = i
			elif (i - pre[c[i]] - 1) % 2 == 0:
				ans[c[i]][-1] += 1
				pre[c[i]] = i
		for i in range(1, n + 1):
			if len(ans[i]) == 0:
				print(0, end=' ')
			else:
				print(max(ans[i]), end=' ')
		print()
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	res = [0] * n
	for i in range(n):
		arr[i] -= 1
		if res[arr[i]] == 0:
			res[arr[i]] = 1
	seen = {}
	for i in range(n):
		color = arr[i]
		if color not in seen:
			seen[color] = i
		else:
			if (i - seen[color]) % 2 == 1:
				res[color] += 1
			seen[color] = i
	for val in res:
		print(val, end=' ')
	print()


for s in [*open(0)][2::2]:
	a = s.split()
	r = [[] for _ in a]
	i = 0
	for x in a:
		l = r[int(x) - 1]
		l += ([], [i])[l == [] or i - l[-1] & 1]
		i += 1
	print(*map(len, r))


cases = int(input())
for _ in range(cases):
	n = int(input())
	last_index = [None] * (n + 1)
	height = [0] * (n + 1)
	colors = list(map(lambda x: int(x), input().split(' ')))
	for i in range(len(colors)):
		if last_index[colors[i]] == None:
			last_index[colors[i]] = i
			height[colors[i]] += 1
		elif (i - last_index[colors[i]] - 1) % 2 == 0:
			last_index[colors[i]] = i
			height[colors[i]] += 1
	for i in range(1, n + 1):
		print(height[i], end=' ')
	print()


T = int(input())
while T:
	n = int(input())
	l = list(map(int, input().split()))
	info = {}
	for i in range(n):
		if l[i] not in info:
			info[l[i]] = [i, 1]
		elif (i - info[l[i]][0] - 1) % 2 == 0:
			t = info[l[i]][1] + 1
			info[l[i]] = [i, t]
		else:
			info[l[i]][0] = i
	for j in range(1, n + 1):
		if j not in info:
			print(0, end=' ')
		else:
			print(info[j][1], end=' ')
	print()
	T -= 1


for t in range(int(input())):
	n = int(input())
	steps = list(map(lambda x: [0, 0], range(n)))
	for (idx, c) in enumerate(map(int, input().split(' '))):
		steps[c - 1][idx % 2] = steps[c - 1][(idx + 1) % 2] + 1
	print(*list(map(max, steps)))


testcase = int(input())
for _ in range(testcase):
	n = int(input())
	arr = [int(num) for num in input().split()]
	stackes = [[] for _ in range(n)]
	for (ind, num) in enumerate(arr):
		stackes[num - 1].append(ind)
	ans = []
	for ArrStack in stackes:
		if not ArrStack:
			ans.append(0)
			continue
		t = [ArrStack[0] % 2]
		for num in ArrStack[1:]:
			if num % 2 == t[-1]:
				continue
			t.append(num % 2)
		ans.append(len(t))
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	l = [[0, 0] for i in range(n + 1)]
	for (i, x) in enumerate(a):
		if l[x][0] == 0 or (i - l[x][1]) % 2:
			l[x][0] += 1
			l[x][1] = i
	print(*[x[0] for x in l[1:]])


t = int(input())
while t:
	p = int(input())
	g = [[] for i in range(p + 1)]
	s = list(map(int, input().split()))
	for i in range(p):
		g[s[i]].append(i)
	l = [0] * p
	for i in range(1, p + 1):
		if len(g[i]) >= 1:
			check = 1
			for k in range(1, len(g[i])):
				if (g[i][k] - g[i][k - 1]) % 2 == 1:
					check += 1
			l[i - 1] = check
	print(*l)
	t -= 1


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	colors = list(map(int, input().split()))
	last_index = dict()
	ans_val = defaultdict(int)
	for (i, c) in enumerate(colors):
		if c not in last_index:
			last_index[c] = i
			ans_val[c] = 1
		elif (i - last_index[c]) % 2 == 1:
			last_index[c] = i
			ans_val[c] += 1
	for i in range(1, n + 1):
		print(ans_val[i], end='' if i == n else ' ')
	print()


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d1 = {}
	for i in range(n):
		if l[i] in d1:
			d1[l[i]].append(i)
		else:
			d1[l[i]] = [i]
	for i in range(1, n + 1):
		if i in d1:
			c = 1
			if len(d1[i]) == 1:
				l[i - 1] = c
			else:
				for j in range(1, len(d1[i])):
					if (d1[i][j] - d1[i][j - 1]) % 2 == 1:
						c += 1
				l[i - 1] = c
		else:
			l[i - 1] = 0
	print(*l)


from collections import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		if not d[a[i]]:
			d[a[i]].append(i)
		elif (i - d[a[i]][-1] - 1) % 2 == 0:
			d[a[i]].append(i)
	ans = []
	for i in range(1, n + 1):
		ans.append(len(d[i]))
	print(*ans)


for _ in [0] * int(input()):
	n = int(input())
	(*c,) = map(int, input().split())
	b = [[0, -1] for i in range(n + 1)]
	for i in range(n):
		if (i - b[c[i]][1]) % 2 or b[c[i]][1] == -1:
			b[c[i]][0] += 1
		b[c[i]][1] = i
	for i in range(n):
		print(b[i + 1][0], end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	d = {}
	cnt = {}
	for i in range(n):
		if c[i] in d:
			x = i - d[c[i]]
			if x % 2 == 1:
				if c[i] in cnt:
					cnt[c[i]] += 1
				else:
					cnt[c[i]] = 2
		d[c[i]] = i
	for k in range(1, n + 1):
		if k in cnt:
			print(cnt[k], end=' ')
		elif k in d:
			print(1, end=' ')
		else:
			print(0, end=' ')
	print()