Chef has N dishes of different types arranged in a row: A_{1}, A_{2}, \ldots, A_{N}, where A_{i} denotes the type of the i^{th} dish. He wants to choose as many dishes as possible from the given list but while satisfying two conditions: 

1.  He can choose only one type of dish.   
2.  No two chosen dishes should be adjacent to each other. 

Chef wants to know which type of dish he should choose from, so that he can pick the maximum number of dishes.

Example:      
Given N=9 and A=[1, 2, 2, 1, 2, 1, 1, 1, 1].   
For type 1, Chef can choose at most four dishes. One of the ways to choose four dishes of type 1 is A_{1}, A_{4}, A_{7} and A_{9}.   
For type 2, Chef can choose at most two dishes. One way is to choose A_{3} and A_{5}.  
So in this case, Chef should go for type 1, in which he can pick more dishes.

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

- The first line contains T, the number of test cases. Then the test cases follow.
- For each test case, the first line contains a single integer N.
- The second line contains N integers A_{1}, A_{2}, \ldots, A_{N}. 

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

For each test case, print a single line containing one integer ― the type of the dish that Chef should choose from. If there are multiple answers, print the smallest one.

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

$1 ≤T ≤10^{3}$
$1 ≤N ≤10^{3}$
$1 ≤A_{i} ≤10^{3}$
- Sum of $N$ over all test cases doesn't exceed $10^{4}$

----- Sample Input 1 ------ 
3
5
1 2 2 1 2
6
1 1 1 1 1 1
8
1 2 2 2 3 4 2 1
----- Sample Output 1 ------ 
1
1
2
----- explanation 1 ------ 
Test case 1:   
For both type 1 and type 2, Chef can pick at most two dishes. In the case of multiple answers, we pick the smallest one. Hence the answer will be $1$.

Test case 2:   
There are only dishes of type 1. So the answer is $1$.

Test case 3:   
For type 1, Chef can choose at most two dishes. For type 2, he can choose three dishes. For type 3 and type 4, Chef can choose the only dish available. Hence the maximum is in type 2 and so the answer is $2$.

Difficulty: EASY
Tags: Complete search

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
from collections import Counter
t = int(input())
for jfhf in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	uni = set(a)
	num_uni = len(uni)
	count = Counter(a)
	i = 0
	while i < n - 1:
		if a[i + 1] == a[i]:
			count[a[i]] -= 1
			i += 2
		else:
			i += 1
	m = 0
	for j in count:
		if count[j] > m:
			m = count[j]
			indx = j
		if count[j] == m:
			r = min(indx, j)
			indx = r
	print(indx)


T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	counts = {}
	counts[A[0]] = 1
	for i in range(1, N):
		if A[i] in counts and A[i - 1] != A[i]:
			counts[A[i]] += 1
		elif A[i] not in counts and A[i - 1] != A[i]:
			counts[A[i]] = 1
		else:
			A[i] = None
	maxi = -1
	final = None
	for i in sorted(counts):
		if counts[i] > maxi:
			maxi = counts[i]
			final = i
	print(final)


T = int(input())
sumofn = 0
if T < 1 or T > 1000:
	print('Tescase number must be between 1 and 1000')
else:
	for i in range(0, T):
		N = int(input())
		if N < 1 or N > 1000:
			print('N value must be between 1 and 1000')
		else:
			sumofn = sumofn + N
			l = map(int, input().split())
			l = list(l)
			typeofdishvalid = True
			for i in l:
				if i < 1 or i > 1000:
					typeofdishvalid = False
			if typeofdishvalid == True:
				types = []
				for i in l:
					if i not in types:
						types.append(i)
				amountoftype = []
				c = 0
				for key in types:
					c = 0
					t = 0
					while True:
						if key == l[t]:
							c = c + 1
							t = t + 2
						else:
							t = t + 1
						if t >= len(l):
							break
					amountoftype.append(c)
				m = 10000
				for i in range(0, len(amountoftype)):
					if max(amountoftype) == amountoftype[i]:
						if types[i] < m:
							m = types[i]
				print(m)
if sumofn > 10000:
	print('Ignore all outputs, sum of all N values too large')


import random
t = int(input())
for z in range(t):
	biggest = 0
	n = int(input())
	inp = input()
	a = inp.split()
	a = [int(ele) for ele in a]
	d = {}
	d[a[0]] = 1
	for n in range(1, len(a), 1):
		if a[n] not in d and a[n] != a[n - 1]:
			d[a[n]] = 1
		elif a[n] in d and a[n] != a[n - 1]:
			d[a[n]] = d[a[n]] + 1
		else:
			a[n] = 0
	for n in sorted(d):
		if d[n] > biggest:
			biggest = d[n]
			key = n
	print(key)


T = int(input())
for c in range(0, T, 1):
	a = int(input())
	n = [int(x) for x in input().split()]
	final = ''
	d = {}
	for i in n:
		if i == final:
			final = ''
		else:
			d[i] = d.get(i, 0) + 1
			final = i
	(min_i, maxvalue) = (0, 0)
	for (x, y) in d.items():
		if y > maxvalue or (y == maxvalue and x < min_i):
			maxvalue = y
			min_i = x
	print(min_i)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	cur = ''
	d = {}
	for i in a:
		if i == cur:
			cur = ''
		else:
			d[i] = d.get(i, 0) + 1
			cur = i
	(min_i, max_value) = (0, 0)
	for (x, y) in d.items():
		if y > max_value or (y == max_value and x < min_i):
			max_value = y
			min_i = x
	print(min_i)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	z = list(set(l))
	z.sort()
	fst = l[0]
	for i in range(1, len(l)):
		if fst == l[i]:
			l[i] = -1
			fst = l[i]
		else:
			fst = l[i]
	d = []
	for j in z:
		d.append(l.count(j))
	print(z[d.index(max(d))])


cases = int(input())
for case in range(cases):
	n = int(input())
	dishes = list(map(int, input().split()))
	unqiueVals = list(set(dishes))
	maxDish = [0, 0]
	for val in unqiueVals:
		selected = []
		for dish in range(len(dishes)):
			if dishes[dish] == val:
				if dish == 0:
					if dish + 1 not in selected:
						selected.append(dish)
				elif dish == len(dishes):
					if dish - 1 not in selected:
						selected.append(dish)
				elif dish - 1 not in selected and dish + 1 not in selected:
					selected.append(dish)
		if len(selected) > maxDish[1]:
			maxDish[0] = val
			maxDish[1] = len(selected)
		elif len(selected) == maxDish[1]:
			if maxDish[0] > val:
				maxDish[0] = val
				maxDish[1] = len(selected)
	print(maxDish[0])


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n):
		if a[i] == a[i - 1]:
			a[i] = 0
	while 0 in a:
		a.remove(0)
	n = len(a)
	for i in range(n):
		for j in range(0, n - i - 1):
			if a[j] > a[j + 1]:
				temp = a[j]
				a[j] = a[j + 1]
				a[j + 1] = temp
	max_count = 0
	max_num = a[0]
	for num in a:
		count = a.count(num)
		if count > max_count:
			max_count = count
			max_num = num
	print(max_num)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = set(l)
	l += [-1]
	for i in range(n):
		if l[i] == l[i + 1]:
			l[i + 1] = 0
	l.pop(-1)
	ans = float('inf')
	d = {x: l.count(x) for x in l1 if x != 0}
	m = max(list(d.values()))
	for i in d:
		if m == d[i]:
			ans = min(ans, i)
	print(ans)


from statistics import mode
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n):
		if a[i] == a[i - 1]:
			a[i] = 0
	for k in a:
		if k == 0:
			a.remove(k)
	a = sorted(a)
	print(max(a, key=a.count))


t = int(input())
for i in range(t):
	n = int(input())
	dish = [int(x) for x in input().split()]
	freq = {}
	freq[dish[0]] = 1
	for j in range(1, n):
		if dish[j] in freq and dish[j - 1] != dish[j]:
			freq[dish[j]] += 1
		elif dish[j] not in freq and dish[j - 1] != dish[j]:
			freq[dish[j]] = 1
		else:
			dish[j] = -1
	maxval = -1
	maxkey = -1
	for i in sorted(freq):
		if freq[i] > maxval:
			maxkey = i
			maxval = freq[i]
	print(maxkey)


t = int(input())
for i in range(t):
	n = int(input())
	d = input().split(' ')
	for j in range(n):
		d[j] = int(d[j])
	j = 1
	while j < n:
		if d[j] == d[j - 1]:
			d.pop(j)
			n = n - 1
		j = j + 1
	print(min([a for a in d if d.count(a) == max([d.count(x) for x in d])]))


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			arr[i + 1] = 0
		else:
			pass
	while 0 in arr:
		arr.remove(0)
	d = {}
	for k in arr:
		if k in d:
			d[k] += 1
		else:
			d[k] = 1
	s = sorted(d.items(), key=lambda x: (-x[-1], x[0]))
	print(s[0][0])


from collections import Counter
t = int(input())
while t > 0:
	c = 0
	v = 0
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n - 1):
		if l[i + 1] == l[i]:
			l[i + 1] = 0
	l = Counter(l)
	for i in l:
		if i != 0:
			if v < l.get(i):
				v = l.get(i)
				c = i
			elif v == l.get(i):
				if c > i:
					c = i
	print(c)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	for j in range(len(a) - 1):
		if a[j + 1] == a[j]:
			a[j + 1] = 0
		else:
			pass
	a = list(filter(lambda y: y != 0, a))
	print(max(sorted(set(a)), key=a.count))


for x in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ls = set(l)
	dic = {}
	dic2 = {}
	for i in ls:
		dic[i] = []
		dic2[i] = 1
	for i in range(n):
		dic[l[i]].append(i)
	for (i, j) in enumerate(dic):
		arr = dic[j]
		last_pos = -2
		temp = 0
		for m in range(len(arr)):
			if arr[m] - last_pos > 1:
				last_pos = arr[m]
				temp += 1
		dic2[j] = temp
	top = -1
	el = -2
	for (i, k) in enumerate(dic2):
		if top < dic2[k] or (top == dic2[k] and k < el):
			top = dic2[k]
			el = k
	print(el)


T = int(input())
for i in range(0, T):
	n = int(input())
	l = list(map(int, input().split()))
	maxL = 0
	ans = 10000000
	mp = {}
	for i in range(0, n):
		if l[i] in mp:
			if i - mp[l[i]][-1] > 1:
				mp[l[i]].append(i)
		else:
			mp[l[i]] = [i]
	for i in mp:
		temp = len(mp[i])
		if temp > maxL:
			maxL = temp
			ans = i
		if temp == maxL:
			ans = min(ans, i)
	print(ans)


def fun(lst, N):
	for i in range(N - 1):
		if lst[i] == lst[i + 1]:
			lst[i + 1] = 0
T = int(input())
for _ in range(T):
	N = int(input())
	lst = list(map(int, input().split()))
	fun(lst, N)
	lst.sort()
	zero = lst.count(0)
	lst = lst[zero:]
	newlst = [lst.count(i) for i in set(lst)]
	occr = max(newlst)
	for i in lst:
		if lst.count(i) == occr:
			print(i)
			break


T = int(input())
for X in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	for k in range(len(A) - 1):
		if A[k + 1] == A[k]:
			A[k + 1] = 0
		else:
			pass
	A = list(filter(lambda a: a != 0, A))
	print(max(sorted(set(A)), key=A.count))


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	A_new = []
	i = 0
	while i < n:
		if i < n - 1:
			if A[i] == A[i + 1]:
				A_new.append(A[i + 1])
				i = i + 2
			else:
				A_new.append(A[i])
				i = i + 1
		elif i == n - 1:
			A_new.append(A[i])
			i = i + 1
	d = {}
	for i in A_new:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	values = list(d.values())
	keys = list(d.keys())
	highest = max(values)
	if values.count(highest) > 1:
		keys_new = []
		i = 0
		while i < len(values):
			if values[i] == highest:
				keys_new.append(keys[i])
			i = i + 1
		print(min(keys_new))
	else:
		print(keys[values.index(highest)])


t = int(input())
for i in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	mydict = dict()
	num2 = set(num)
	for ele in num2:
		count = 0
		pos = -1
		for k in range(len(num)):
			if ele == num[k]:
				if k > pos + 1 or k == 0:
					count += 1
					pos = k
		mydict[ele] = count
	sorteddict = dict(sorted(mydict.items(), key=lambda x: x[1]))
	maxnum = list(sorteddict.values())[-1]
	dish = list()
	for key in sorteddict:
		if sorteddict[key] == maxnum:
			dish.append(key)
	print(min(dish))


T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	if len(L) == 1:
		print(L[0])
	else:
		i = 1
		while i < len(L):
			if L[i] == L[i - 1]:
				L.pop(i)
			i += 1
		maxi_count = -1
		maxi_item = -1
		for item in set(L):
			item_count = L.count(item)
			if item_count > maxi_count:
				maxi_count = item_count
				maxi_item = item
			elif item_count == maxi_count:
				maxi_item = min(maxi_item, item)
		print(maxi_item)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(set(a))
	c = [1] * len(b)
	for i in range(len(b)):
		x = a.index(b[i])
		for k in range(n - 1):
			if a[k] == b[i]:
				if k > x + 1:
					c[i] += 1
					x = k
		if a[n - 1] == b[i]:
			if x < n - 2:
				c[i] += 1
	print(b[c.index(max(c))])


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	best = 10000
	best_count = 0
	for dish_type in set(array):
		last_pick = -2
		counter = 0
		for i in range(n):
			if array[i] == dish_type and i - last_pick > 1:
				counter += 1
				last_pick = i
		if counter > best_count:
			best_count = counter
			best = dish_type
		elif counter == best_count:
			best = min(best, dish_type)
	print(best)


from math import *
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	d = dict()
	f = []
	while i < n:
		j = i + 1
		while j < n and l[i] == l[j]:
			j += 1
		d[l[i]] = d.get(l[i], 0) + ceil((j - i) / 2)
		i = j
	m = max(d.values())
	for i in d.keys():
		if d[i] == m:
			f.append(i)
	print(min(f))


import numpy as np
t = int(input())
for i in range(t):
	n = int(input())
	dishes = list(map(int, input().split()))
	count = np.zeros((max(dishes),))
	for j in range(n):
		if dishes[j] != 0:
			count[dishes[j] - 1] += 1
		if j == n - 1:
			pass
		elif dishes[j] == dishes[j + 1]:
			dishes[j + 1] = 0
	count = list(count)
	print(count.index(max(count)) + 1)


from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	used = set()
	dico = defaultdict(int)
	for i in range(len(A)):
		if i == 0 or (A[i] == A[i - 1] and i - 1 not in used) or A[i] != A[i - 1]:
			dico[A[i]] += 1
			used.add(i)
	maxval = max(dico.values())
	res = float('inf')
	for val in dico:
		if dico[val] == maxval:
			res = min(res, val)
	print(res)


T = int(input())
for t in range(T):
	N = int(input())
	dishes = list(map(int, input().split()))
	nbChoicesMax = 0
	lenD = len(dishes)
	types = set(dishes)
	for typeDish in types:
		nbChoices = 0
		i = 0
		while i < lenD:
			if dishes[i] == typeDish:
				nbChoices += 1
				i += 1
			i += 1
		if nbChoices > nbChoicesMax or (nbChoices == nbChoicesMax and typeDish < sol):
			nbChoicesMax = nbChoices
			sol = typeDish
	print(sol)


n = int(input())
for i in range(n):
	N = int(input())
	x = list(map(int, input().split()))
	if len(set(x)) == 1:
		print(x[0])
	else:
		alpha = {}
		i = 0
		while i < len(x):
			if x[i] not in alpha:
				alpha.setdefault(x[i], 1)
			else:
				alpha[x[i]] += 1
			if i != len(x) - 1 and x[i + 1] == x[i]:
				i += 2
			else:
				i += 1
		beta = []
		p = max(alpha.values())
		m = list(alpha.keys())
		n = list(alpha.values())
		for j in range(len(n)):
			if n[j] == p:
				beta.append(m[j])
		print(min(beta))


for _ in range(int(input())):
	n = int(input())
	arr = list((int(i) for i in input().split()))
	total = 0
	dish = arr[0]
	for i in set(arr):
		c = 0
		j = 1
		if arr[0] == i:
			c += 1
			j += 1
		while j < len(arr):
			if arr[j] == i:
				c += 1
				j += 1
			j += 1
		if c > total:
			total = c
			dish = i
		if c == total:
			dish = min(dish, i)
	print(dish)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = [i]
		elif d[a[i]][-1] < i - 1:
			d[a[i]].append(i)
	m = [0, 0]
	for i in d:
		if len(d[i]) > m[1]:
			m = [i, len(d[i])]
		elif len(d[i]) == m[1]:
			m = [min(m[0], i), len(d[i])]
	print(m[0])


from collections import defaultdict
get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	A = get_mint()
	D = defaultdict(list)
	max_cnt = 0
	dish = 1001
	for i in range(N):
		if not D[A[i]] or D[A[i]][-1] + 1 < i:
			D[A[i]].append(i)
			if len(D[A[i]]) > max_cnt:
				dish = A[i]
				max_cnt = len(D[A[i]])
			elif len(D[A[i]]) == max_cnt and dish > A[i]:
				dish = A[i]
	print(dish)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max = 10 ** 3 + 2
	left = 0
	flag = 'No'
	s = {}
	for i in range(n):
		if i == 0:
			left = max
		else:
			left = a[i - 1]
		if a[i] != left:
			if a[i] in s:
				s[a[i]] += 1
			else:
				s[a[i]] = 1
			flag = 'Yes'
		elif a[i] == left and flag == 'No':
			if a[i] in s:
				s[a[i]] += 1
			else:
				s[a[i]] = 1
			flag = 'Yes'
		else:
			flag = 'No'
	count = 0
	ans = max
	for (key, value) in s.items():
		if value > count:
			count = value
			ans = key
		elif value == count and key < ans:
			ans = key
	print(ans)


for _ in range(int(input())):
	input()
	i = list(map(int, input().split()))
	num1 = 0
	num2 = 0
	for ind in range(len(i) - 1):
		if i[ind] == i[ind + 1]:
			i[ind + 1] = 0
	for char in i:
		if char == 0:
			i.remove(char)
	i = sorted(i)
	print(max(i, key=i.count))


import collections
t = int(input())
for i in range(t):
	l = int(input())
	a = [None] * l
	b = [None] * l
	a = list(map(int, input().split()))
	a.append(0)
	c = 1
	count = 0
	for i in range(len(a) - 1):
		if a[i] == a[i + 1]:
			c = c + 1
		if a[i] != a[i + 1]:
			if c > 1:
				c = c - int(c / 2)
			for x in range(c):
				b[count] = a[i]
				count = count + 1
			c = 1
	b = list(filter(None, b))
	b = sorted(b)
	f = collections.Counter(b)
	f = max(f, key=f.get)
	print(f)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	S = set(A)
	D1 = dict()
	D2 = dict()
	for i in S:
		l = list()
		for j in range(len(A)):
			if i == A[j]:
				l.append(j)
		D1[i] = l
	for (x, y) in D1.items():
		a = -10
		cnt = 0
		d = 0
		for i in y:
			if a + 1 != i:
				cnt += 1
				d = 0
			else:
				d += 1
				if d == 2:
					cnt += 1
					d = 0
			a = i
		D2[x] = cnt
	max_d2 = max(D2.values())
	ans = list()
	for (x, y) in D2.items():
		if max_d2 == y:
			ans.append(x)
	print(min(ans))


num = int(input())
for i in range(num):
	count = 0
	n = int(input())
	ls = list(map(int, input().split()))
	d = []
	for t in range(0, n - 1):
		if ls[t] == 0:
			continue
		elif ls[t] == ls[t + 1]:
			ls[t + 1] = 0
	for m in ls:
		if m != 0:
			d.append(m)
	d.sort()
	print(max(d, key=d.count))


t = input()
for c in range(0, int(t)):
	b = int(input())
	c = list(map(int, input().split()))
	d = set(c)
	dict_of_counts = {}
	count = 0
	for i in d:
		count += 1
		index = c.index(i)
		dummy_index = index
		for j in range(index + 1, b):
			if c[j] == c[dummy_index] and j - dummy_index > 1:
				count += 1
				dummy_index = j
		dict_of_counts[i] = count
		count = 0
	maxi = max(dict_of_counts.values())
	final = []
	for (key, value) in dict_of_counts.items():
		if value == maxi:
			final.append(key)
	print(min(final))


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	f = {}
	i = 0
	c = 0
	while i < n:
		x = arr[i]
		while i < n and arr[i] == x:
			i += 1
			c += 1
		if x in f:
			f[x] += math.ceil(c / 2)
		else:
			f[x] = math.ceil(c / 2)
		c = 0
	mj = 0
	ans = None
	for (i, j) in f.items():
		if j > mj:
			mj = j
			ans = i
		elif j == mj:
			ans = min(ans, i)
	print(ans)


for _ in range(int(input())):
	N = int(input())
	numbers = input().split()
	for i in range(N):
		numbers[i] = int(numbers[i])
	remebered = []
	dic = {}
	for i in range(N):
		count = 0
		found = False
		if numbers[i] in remebered:
			continue
		remebered.append(numbers[i])
		for j in range(i, N, 1):
			if found == True:
				found = False
				continue
			elif numbers[j] == numbers[i]:
				found = True
				count += 1
		dic[numbers[i]] = count
	max = None
	for key in dic:
		if max is None:
			max = dic[key]
			dish = key
		elif dic[key] > max:
			max = dic[key]
			dish = key
	for key in dic:
		if key <= dish and dic[key] == dic[dish]:
			dish = key
	print(dish)


for _ in range(int(input())):
	n = int(input())
	arr = [int(j) for j in input().split()]
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			arr[i + 1] = 0
	for x in arr:
		if x == 0:
			arr.remove(x)
	arr.sort()
	print(max(arr, key=arr.count))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(0, n - 1):
		if l[i] == l[i + 1]:
			l[i + 1] = 0
	for x in l:
		if x == 0:
			l.remove(x)
	l.sort()
	print(max(l, key=l.count))


t = int(input())
for _ in range(0, t):
	n = int(input())
	x = list(map(int, input().split()))
	dct = dict()
	l1 = []
	for i in range(0, n - 1):
		if x[i] == x[i + 1]:
			x[i + 1] = 0
	for i in x:
		if i == 0:
			x.remove(i)
	x.sort()
	ans = max(x, key=x.count)
	print(ans)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			l[i + 1] = 0
	for i in l:
		if i != 0:
			a.append(i)
	a.sort()
	ans = max(a, key=a.count)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for _ in range(n - 1):
		if l[_] == l[_ + 1]:
			l[_ + 1] = 0
	for _ in l:
		if _ != 0:
			l1.append(_)
	l1.sort()
	x = max(l1, key=l1.count)
	print(x)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			a[i + 1] = 0
	v = []
	for i in a:
		if i != 0:
			v.append(i)
	v.sort()
	x = max(v, key=v.count)
	print(x)


a = int(input())
for i in range(a):
	b = int(input())
	list_a = list(map(int, input().split()))
	new_list = []
	for j in range(b - 1):
		if list_a[j] == 0:
			continue
		elif list_a[j] == list_a[j + 1]:
			list_a[j + 1] = 0
	for item in list_a:
		if item != 0:
			new_list.append(item)
	new_list.sort()
	output = max(new_list, key=new_list.count)
	print(output)


for _ in range(int(input())):
	n = int(input())
	L = [int(i) for i in input().split()]
	d = {}
	i = 0
	while i < n:
		if L[i] not in d:
			d.update({L[i]: 1})
			x = L[i]
		elif x != L[i]:
			d[L[i]] += 1
			x = L[i]
		elif x == L[i]:
			x = 0
		i += 1
	a = max(d.keys())
	maxm = 0
	for j in d:
		if d[j] > maxm:
			maxm = d[j]
			a = j
		elif d[j] == maxm and j < a:
			a = j
	print(a)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	ans = arr[0]
	count_dict = {arr[0]: [1, 0]}
	maximum_count = 1
	for j in range(length):
		if arr[j] in count_dict:
			if j - count_dict[arr[j]][1] > 1:
				count_dict[arr[j]][0] += 1
				count_dict[arr[j]][1] = j
		else:
			count_dict[arr[j]] = [1, j]
		if count_dict[arr[j]][0] > maximum_count:
			maximum_count = count_dict[arr[j]][0]
			ans = arr[j]
		elif count_dict[arr[j]][0] == maximum_count and arr[j] < ans:
			ans = arr[j]
	print(ans)


from collections import Counter

def take_second(elem):
	return elem[1]
for i in range(int(input())):
	length = int(input())
	array = [int(x) for x in input().split()]
	a = Counter(array)
	occurences = []
	for i in a.keys():
		counter = 0
		skip = False
		for j in range(len(array)):
			if array[j] != i:
				continue
			elif skip:
				skip = False
				continue
			elif j == len(array) - 1:
				counter += 1
			elif array[j] == array[j + 1]:
				counter += 1
				skip = True
			else:
				counter += 1
		occurences.append((i, counter))
	occurences = sorted(occurences, key=lambda x: x[1], reverse=True)
	maximum = occurences[0][1]
	maxiList = []
	for i in occurences:
		if i[1] != maximum:
			break
		else:
			maxiList.append(i)
	print(min(maxiList)[0])


n = int(input())
for i in range(n):
	a = int(input())
	b = list(map(int, input().split()))
	x = []
	y = []
	j = 0
	while j < a:
		if b[j] not in x:
			x.append(b[j])
		j += 1
	for k in range(len(x)):
		count = 0
		m = 0
		while m < len(b):
			if x[k] == b[m]:
				count += 1
				m += 2
			else:
				m += 1
		y.append(count)
	c = []
	for i in range(len(y)):
		if y[i] == max(y):
			c.append(x[i])
	print(min(c))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	d = {}
	c = 0
	max_ = [0, 0]
	while c < n:
		t = a[c]
		if not t in d.keys():
			d[t] = 0
		c += 1
		count = 1
		while c < n and t == a[c]:
			count += 1
			c += 1
		d[t] += math.ceil(count / 2)
		if d[t] > max_[1]:
			max_[0] = t
			max_[1] = d[t]
		elif d[t] == max_[1] and t < max_[0]:
			max_[0] = t
	print(max_[0])


def retPos(arr, key):
	ans = list()
	for i in range(len(arr)):
		if arr[i] == key:
			ans.append(i)
	return ans
for _ in range(int(input())):
	n = int(input())
	mList = list(map(int, input().strip().split()))
	mSet = set(mList)
	mDict = dict()
	for item in mSet:
		count = 1
		ans = retPos(mList, item)
		pos = ans[0]
		for i in ans:
			if i > pos + 1:
				count += 1
				pos = i
		mDict[item] = count
	maxc = max(mDict.values())
	sor = sorted(mDict.keys())
	for i in sor:
		if mDict[i] == maxc:
			print(i)
			break


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	value = None
	count = 0
	for i in range(len(a)):
		d = a[i]
		temp = 0
		j = i
		while j < len(a):
			if a[j] == d:
				temp += 1
				j += 2
			else:
				j += 1
		if count == temp:
			value = min(a[i], value)
		elif temp > count:
			count = temp
			value = a[i]
	print(value)


t = int(input())
for l in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	types = {}
	for i in range(n):
		if a[i] not in types:
			types[a[i]] = [1, 0]
	for i in range(n):
		if i > 0 and a[i - 1] != a[i] or types[a[i]][0]:
			types[a[i]][1] += 1
			types[a[i]][0] = 0
		elif a[i - 1] == a[i]:
			types[a[i]][0] = 1
	(ans, x) = (0, 0)
	for i in types:
		if types[i][1] > x:
			x = types[i][1]
			ans = i
	for i in types:
		if x == types[i][1] and ans > i:
			ans = i
	print(ans)


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	ans = []
	m = 0
	i = 0
	while i < len(a):
		j = i
		l = []
		d = a[i]
		l.append(d)
		while j < len(a):
			if a[j] == d:
				l.append(d)
				j += 2
			else:
				j += 1
		if len(l) == m:
			ans.append(d)
		elif len(l) > m:
			m = len(l)
			ans = []
			x = d
			ans.append(d)
		i += 1
	print(min(ans))


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(j) for j in str(input()).split(' ')]
	j = 0
	m = 0
	h = []
	while j < len(a):
		d = a[j]
		k = j
		l = []
		l.append(d)
		while k < len(a):
			if a[k] == d:
				l.append(d)
				k = k + 2
			else:
				k = k + 1
		if len(l) == m:
			h.append(d)
		if len(l) > m:
			h = []
			m = len(l)
			x = d
			h.append(d)
		j = j + 1
	print(min(h))


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	max = z = 0
	for j in s:
		val = f = 0
		for k in range(N):
			if f == 1 and l[k] == l[k - 1]:
				f = 0
				continue
			if j == l[k]:
				val += 1
				f = 1
		if val > max:
			(max, z) = (val, j)
		elif val == max and j < z:
			z = j
	print(z)


import math
t = int(input())
for i in range(t):
	n = int(input())
	nums = [int(x) for x in input().split(' ')]
	j = 0
	store = {}
	while j < n - 1:
		count = 1
		while j < n - 1 and nums[j + 1] == nums[j]:
			count += 1
			j += 1
		try:
			store[nums[j]] += math.ceil(count / 2)
		except KeyError:
			store[nums[j]] = math.ceil(count / 2)
		j += 1
	if nums[n - 1] != nums[n - 2]:
		try:
			store[nums[n - 1]] += 1
		except KeyError:
			store[nums[n - 1]] = 1
	maxDishes = 0
	minVal = nums[0]
	for (key, val) in store.items():
		if val > maxDishes:
			maxDishes = val
			minVal = key
		elif val == maxDishes and key < minVal:
			minVal = key
	print(minVal)


t = int(input())
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	N = list()
	for x in range(max(L) + 1):
		N.append(0)
	for i in range(len(L)):
		if L[i] != 0 and i != 0:
			if L[i] != L[i - 1]:
				N[L[i]] = N[L[i]] + 1
			else:
				L[i] = 0
		elif L[i] != 0 and i == 0:
			N[L[i]] = N[L[i]] + 1
	print(N.index(max(N)))


t = int(input())
for __ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = set(l)
	res = 0
	val = l[0]
	for k in l1:
		count = 0
		pre = -2
		for i in range(len(l)):
			if l[i] == k and i - 1 != pre:
				count += 1
				pre = i
		if count == res:
			val.append(k)
		if count > res:
			res = count
			val = [k]
	val.sort()
	print(val[0])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = set(l)
	k = list(t)
	k.sort()
	final = []
	for x in k:
		count = 0
		for y in range(n):
			if l[y] == x:
				if count == 0:
					prev = y
				if y - prev != 1:
					count += 1
					prev = y
		final.append(count)
	maxm = max(final)
	ind = final.index(maxm)
	print(k[ind])


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	diff_l = list(set(l))
	diff_l.sort()
	if len(diff_l) == 1:
		print(diff_l[0])
	else:
		count_list = []
		for i in range(len(diff_l)):
			c = 0
			index = l.index(diff_l[i])
			for j in range(n):
				if l[j] == diff_l[i]:
					if j - index > 1 or index - j > 1:
						c = c + 1
						index = j
			count_list.append(c + 1)
		i = count_list.index(max(count_list))
		print(diff_l[i])


for _ in range(int(input())):
	n = int(input())
	dishes = list(map(int, input().split()))
	maxx = 0
	for i in set(dishes):
		currmax = 0
		counter = 0
		while counter < n:
			if dishes[counter] == i:
				currmax += 1
				counter += 2
			else:
				counter += 1
		if currmax > maxx:
			maxx = currmax
			overallmax = i
			maxdish = i
		elif currmax == maxx:
			overallmax = min(i, maxdish)
			maxdish = overallmax
	print(overallmax)


def main():
	T = int(input())
	for counter in range(T):
		ans = 0
		memo = {}
		n = int(input())
		a = list(map(int, input().split()))
		for i in range(n):
			if a[i] in memo:
				if memo[a[i]][-1] != i - 1:
					memo[a[i]].append(i)
			else:
				memo[a[i]] = [i]
		maximum = 0
		for items in a:
			if maximum == len(memo[items]) and items < ans:
				ans = items
			elif maximum < len(memo[items]):
				maximum = len(memo[items])
				ans = items
		print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dish = {}
	for i in range(n):
		if arr[i] not in dish:
			dish[arr[i]] = 1
		elif arr[i] in dish and arr[i] != arr[i - 1]:
			dish[arr[i]] = dish.get(arr[i]) + 1
		elif arr[i] in dish and arr[i] == arr[i - 1]:
			arr[i] = '_'
	keys = list(dish.keys())
	values = list(dish.values())
	poss_dish = []
	for i in range(len(values)):
		if values[i] == max(values):
			poss_dish.append(keys[i])
	print(min(poss_dish))


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	ma = -1
	maxc = 0
	while s:
		i = min(s)
		s.remove(i)
		count = 0
		j = 0
		while j < n:
			if l[j] == i:
				count += 1
				j += 1
			j += 1
		if count > maxc:
			ma = i
			maxc = count
	print(ma)