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: interview

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
 # print(l)
 m=0
 sx=list(s)
 sx.sort()
 for i in sx:
  x=l.count(i)
  if m<x:
   m=x
   z=i
  
 print(z)

# cook your dish here
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 27 21:08:53 2020

@author: pavan
"""

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))])
 
 
# 3
# 5
# 1 2 2 1 2
# 6
# 1 1 1 1 1 1
# 8
# 1 2 2 2 3 4 2 1


# cook your dish here
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 27 23:13:37 2020

@author: SRILEKHA
"""


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])
   #print(i+1)
  else:
   if L[i]==L[i+1]:
    A.append(L[i+1])
    #print(i+2)
    i=i+1
   else:
    A.append(L[i])
    #print(i+1)
  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))
 
 


# cook your dish here
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

# cook your dish here
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)) 

# cook your dish here
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(i,a[i],types)
 print(types.index(max(types)))

# cook your dish here
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
  #print(list_hai_bhai)
  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
  #print(dic)
  if verma==1:
   dic.pop(-1)
  #print(dic)
  print(max(dic,key=dic.get) )
except:
 pass

# cook your dish here
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:
   # print('A')
   NewA.append(A[i])
   num[A[i]] += 1
   if flag:
    # print('B')
    flag = False
  else:
   flag = True
   # print('C')
  # print(NewA,i)
 # print(NewA)
 # print(num)
 print(num.index(max(num)))




# cook your dish here
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
  else:
   if (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()

# cook your dish here
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))])

# cook your dish here
# cook your dish here
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)