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: 
- He can choose only one type of dish.   
- 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:-----
- 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:-----
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 \le T \le 10^3$
- $1 \le N \le 10^3$
- $1 \le A_i \le 10^3$
- Sum of $N$ over all test cases doesn't exceed $10^4$

-----Sample Input:-----
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
2

-----Explanation:-----
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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = int(input())
f = 0
y = 0
for _ in range(t):
	n = int(input())
	seq = [int(x) for x in input().split()]
	prev = seq[0]
	for i in range(1, len(seq)):
		if prev == seq[i]:
			seq[i] = 0
		prev = seq[i]
	ans = 0
	anss = 0
	for el in seq:
		if el != 0:
			c = seq.count(el)
			if ans < c:
				ans = c
				anss = el
			elif ans == c:
				if el < anss:
					anss = el
				else:
					anss = anss
	print(anss)


test = int(input())
for _ in range(test):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	se = set(arr)
	t = 0
	res = 0
	for i in se:
		c = 0
		j = 0
		while j < n:
			if arr[j] == i:
				pp = 0
				while arr[j] == i:
					j += 1
					pp += 1
					if j >= n:
						break
				c += (pp + 1) // 2
			j += 1
		if c > t:
			t = c
			res = i
		if c == t:
			res = min(res, i)
	print(res)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	for i in range(1, n):
		if l[i] == l[i - 1]:
			l[i] = -1
	m = 0
	sx = list(s)
	sx.sort()
	for i in sx:
		x = l.count(i)
		if m < x:
			m = x
			z = i
	print(z)


for _ in range(int(input())):
	N = int(input())
	ls = list(map(int, input().split()))
	types = []
	type_count = []
	for i in ls:
		if i not in types:
			types.append(i)
	types.sort()
	for j in types:
		indices = []
		for k in range(N):
			if ls[k] == j:
				if k - 1 not in indices:
					indices.append(k)
		type_count.append(len(indices))
	print(types[type_count.index(max(type_count))])


for _ in range(int(input())):
	num = int(input())
	length = list(map(int, input().split()))
	temp = []
	ls = []
	for i in length:
		if i not in temp:
			temp.append(i)
	temp.sort()
	for j in temp:
		indices = []
		for k in range(0, num):
			if length[k] == j:
				if k - 1 not in indices:
					indices.append(k)
		ls.append(len(indices))
	print(temp[ls.index(max(ls))])


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	A = []
	L = list(map(int, input().split()))
	i = 0
	while i < n:
		if i == n - 1:
			A.append(L[i])
		elif L[i] == L[i + 1]:
			A.append(L[i + 1])
			i = i + 1
		else:
			A.append(L[i])
		i += 1
	count = Counter(A)
	z = []
	maxvalue = max(count.values())
	for (k, v) in list(count.items()):
		if v == maxvalue:
			z.append(k)
	print(min(z))


try:
	for _ in range(int(input())):
		s1 = int(input())
		po = list(map(int, input().split()))
		yp = set(po)
		mo = []
		sa = [po[0]]
		da = []
		for x in yp:
			mo.append(x)
		mo.sort()
		bun = 0
		cop = po[0]
		for x in range(1, len(po)):
			if po[x] != cop or x - bun > 1:
				sa.append(po[x])
				bun = x
				cop = po[x]
		for x in range(len(mo)):
			da.append(sa.count(mo[x]))
		daa = da.index(max(da))
		print(mo[daa])
except:
	pass


try:
	for _ in range(int(input())):
		n1 = int(input())
		list2 = list(map(int, input().split()))
		set1 = set(list2)
		list3 = []
		list4 = [list2[0]]
		list5 = []
		for i in set1:
			list3.append(i)
		list3.sort()
		m = 0
		n = list2[0]
		for i in range(1, len(list2)):
			if list2[i] != n or i - m > 1:
				list4.append(list2[i])
				m = i
				n = list2[i]
		for i in range(len(list3)):
			list5.append(list4.count(list3[i]))
		val = list5.index(max(list5))
		print(list3[val])
except:
	pass


def selectDish(arr, n):
	res = 0
	maxS = 0
	dd = dict()
	for i in range(n):
		if arr[i] in dd:
			dd[arr[i]].append(i)
		else:
			dd[arr[i]] = [i]
	for dish in dd:
		indexes = dd[dish]
		count = 0
		prevIdx = -2
		for idx in indexes:
			if idx - prevIdx > 1:
				count += 1
				prevIdx = idx
		if count > maxS:
			res = dish
			maxS = count
		elif count == maxS:
			if dish < res:
				res = dish
	return res

def __starting_point():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		print(selectDish(arr, n))
__starting_point()


T = int(input())
while T > 0:
	n = int(input())
	l = list(map(int, input().split()))
	s = list(sorted(set(l)))
	maxx = 0
	ans = 0
	for i in s:
		curr = 0
		j = 0
		while j < n:
			if l[j] == i:
				curr += 1
				j += 2
			else:
				j += 1
		if curr > maxx:
			maxx = curr
			ans = i
	print(ans)
	T -= 1


from collections import Counter
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	keys = list(Counter(a).keys())
	l = []
	for i in range(len(keys)):
		ctr = 0
		j = 0
		while j < n:
			if keys[i] == a[j]:
				ctr += 1
				j = j + 2
			else:
				j += 1
		l.append(ctr)
	x = max(l)
	ll = []
	for i in range(len(l)):
		if l[i] == x:
			ll.append(keys[i])
	print(min(ll))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	types = [0] * 1001
	flag = 0
	for i in range(n):
		if i != 0:
			if a[i - 1] == a[i] and flag == 0:
				flag = 1
				continue
		types[a[i]] += 1
		flag = 0
	print(types.index(max(types)))


try:
	for _ in range(int(input())):
		number = int(input())
		list_hai_bhai = list(map(int, input().split(' ')))
		dic = {}
		verma = 0
		for cv in range(number - 1):
			if list_hai_bhai[cv] == list_hai_bhai[cv + 1]:
				list_hai_bhai[cv + 1] = -1
				verma = 1
		list_hai_bhai.sort()
		for cv in range(number):
			if list_hai_bhai[cv] in dic:
				dic[list_hai_bhai[cv]] += 1
			else:
				dic[list_hai_bhai[cv]] = 1
		if verma == 1:
			dic.pop(-1)
		print(max(dic, key=dic.get))
except:
	pass


T = int(input())
for case in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	NewA = []
	NewA.append(A[0])
	flag = False
	net = 0
	count = 0
	num = [0 for i in range(max(A) + 1)]
	num[A[0]] += 1
	for i in range(1, len(A)):
		if A[i] != A[i - 1] or flag:
			NewA.append(A[i])
			num[A[i]] += 1
			if flag:
				flag = False
		else:
			flag = True
	print(num.index(max(num)))


for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	maxx = 0
	ans = 0
	for i in range(1, max(arr) + 1):
		temp = 0
		ind = 0
		for j in range(N):
			if i == arr[j] and temp == 0:
				temp += 1
				ind = j
			elif i == arr[j] and j - 1 != ind:
				temp += 1
				ind = j
		if temp > maxx:
			maxx = temp
			ans = i
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	d = dict.fromkeys(set(lst), 0)
	d[lst[0]] = 1
	lst[0] *= -1
	for i in range(1, len(lst)):
		if lst[i] != -1 * lst[i - 1]:
			d[lst[i]] += 1
			lst[i] *= -1
	resl = []
	mx = 0
	k = 0
	for i in d:
		if d[i] > mx:
			mx = d[i]
	for i in d:
		if d[i] == mx:
			resl.append(i)
	print(min(resl))


def f():
	n = int(input())
	a = list(map(int, input().split()))
	ind = [] * 1001
	for i in range(0, 1001):
		ind.append([])
	for i in range(0, len(a)):
		ind[a[i]].append(i)
	maxi = 0
	data = 0
	for i in range(1, 1001):
		s = 0
		c = 1
		if len(ind[i]) == 1:
			s = 1
			if maxi < s:
				maxi = s
				data = i
			elif maxi == s:
				data = min(data, i)
			continue
		for j in range(1, len(ind[i])):
			if ind[i][j] - ind[i][j - 1] == 1:
				c += 1
			if ind[i][j] - ind[i][j - 1] != 1:
				s += c // 2 + c % 2
				c = 1
			if j == len(ind[i]) - 1:
				s += c // 2 + c % 2
				c = 1
		if maxi < s:
			maxi = s
			data = i
		elif maxi == s:
			data = min(data, i)
	if len(a) == 1:
		print(a[0])
	else:
		print(data)
for i in range(int(input())):
	f()


def main():
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	d = dict()
	d1 = {}
	for i in s:
		d[i] = [l.index(i), False]
		d1[i] = 1
	for i in range(n):
		if d[l[i]][1] == False:
			d[l[i]][1] = True
			continue
		elif d[l[i]][0] + 1 != i:
			d1[l[i]] += 1
			d[l[i]][0] = i
	maxi = 0
	for i in d1.values():
		if i > maxi:
			maxi = i
	for i in sorted(d1):
		if d1[i] == maxi:
			print(i)
			break
for _ in range(int(input())):
	main()


for T in range(int(input())):
	n = int(input())
	a_lst = list(map(int, input().split()))
	dish_type = []
	dish_type_count = []
	for i in a_lst:
		if i not in dish_type:
			dish_type.append(i)
	dish_type.sort()
	for j in dish_type:
		dish_indices = []
		for k in range(n):
			if a_lst[k] == j:
				if k - 1 not in dish_indices:
					dish_indices.append(k)
		dish_type_count.append(len(dish_indices))
	print(dish_type[dish_type_count.index(max(dish_type_count))])


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	s = list(set(l))
	s.sort()
	arr = []
	for i in s:
		a = []
		for j in range(n):
			if i == l[j]:
				a.append(j)
		arr.append(a)
	if len(arr) == 1:
		print(l[0])
	else:
		count = 1
		m = 0
		c = -1
		for i in arr:
			c += 1
			for j in range(len(i) - 1):
				if j == 0:
					p = i[j]
				if i[j + 1] - p > 1:
					count += 1
					p = i[j + 1]
			if m < count:
				m = count
				x = s[c]
			count = 1
		print(x)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for ele in set(l):
		d[ele] = 0
	i = 0
	while i < n:
		count = 0
		type = l[i]
		while l[i] == type:
			count += 1
			i += 1
			if i == n:
				break
		d[type] += (count + 1) // 2
	ans = min(l)
	for ele in d:
		if d[ele] > d[ans] or (d[ele] == d[ans] and ans > ele):
			ans = ele
	print(ans)