You are given an array $a$ consisting of $n$ integers numbered from $1$ to $n$.

Let's define the $k$-amazing number of the array as the minimum number that occurs in all of the subsegments of the array having length $k$ (recall that a subsegment of $a$ of length $k$ is a contiguous part of $a$ containing exactly $k$ elements). If there is no integer occuring in all subsegments of length $k$ for some value of $k$, then the $k$-amazing number is $-1$.

For each $k$ from $1$ to $n$ calculate the $k$-amazing number of the array $a$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of elements in the array. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the elements of the array. 

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


-----Output-----

For each test case print $n$ integers, where the $i$-th integer is equal to the $i$-amazing number of the array.


-----Example-----
Input
3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1

Output
-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1

Difficulty: interview

Starter code:

Solutions:
input=__import__('sys').stdin.readline
for _ in range(int(input())):
	n=int(input())
	s=list(map(int,input().split()))
	g=[[-1]for _ in range(n+1)]
	for i in range(n):
		g[s[i]].append(i)
	inf=10**10
	ans=[-1]*n
	lstunused=n
	for i in range(1,n+1):
		g[i].append(n)
		mx=0
		for j in range(1,len(g[i])):
			mx=max(mx,g[i][j]-g[i][j-1]-1)
		for j in range(mx,lstunused):
			ans[j]=i
		lstunused=min(lstunused,mx)
	print(*ans)

import sys

    
def main():
    #n = iinput()
    #k = iinput() 
    #m = iinput() 
    n = int(sys.stdin.readline().strip()) 
    #n, k = rinput()
    #n, m = rinput()
    #m, k = rinput()
    #n, k, m = rinput()
    #n, m, k = rinput()
    #k, n, m = rinput()
    #k, m, n = rinput() 
    #m, k, n = rinput()
    #m, n, k = rinput()
    q = list(map(int, sys.stdin.readline().split()))
    #q = linput()
    clovar, p, x = {}, [], 1e9
    for i in range(n):
        if q[i] in clovar:
            clovar[q[i]].append(i)
        else:
            clovar[q[i]] = [i]
    for o in clovar:
        t = clovar[o]
        ma = max(t[0] + 1, n - t[-1])
        dlinat = len(t) - 1
        for i in range(dlinat): 
            ma = max(t[i + 1] - t[i], ma)
        p.append([ma, o])
    p.sort()
    ans = [p[0]]
    dlinap = len(p)
    for i in range(1, dlinap):
        if ans[-1][0] != p[i][0]:
            ans.append(p[i])
    ans.append([n + 1, 1e9])
    dlina_1 = ans[0][0] - 1
    print(*[-1 for i in range(dlina_1)], end=" ")
    dlinaans = len(ans) - 1
    for i in range(dlinaans):
        x = min(x, ans[i][1])
        dlinax = ans[i + 1][0] - ans[i][0]
        print(*[x for o in range(dlinax)], end=" ")
    print()
           
        
            
    
    
    
    
    
    
            
                
        
    
            
        

            
        
    
                
    
    
    
            
    
        
    

for i in range(int(sys.stdin.readline().strip()) ):
    main()
    


import sys
import math
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    
    S = {}
    for el in arr:
        S[el] = [0]
        
    for i in range(len(arr)):
        S[arr[i]].append(i+1)
        
    G = {}
    
    for key in S:
        S[key].append(n+1)
        best = 0
        for i in range(len(S[key]) - 1):
            gap = abs(S[key][i] - S[key][i+1])
            best = max(gap, best)
        G[key] = best
        
    #print(G)
    B = {}
    for key in G:
        l = G[key]
        if l not in B:
            B[l] = key
        else:
            B[l] = min(B[l], key)
            
    ans = []
    for key in B:
        ans.append((key, B[key]))
        
    ans.sort()
    
    pp = []
    low = 9999999999999999
    j = 0
    for i in range(1, n+1):
        if j<len(ans) and i==ans[j][0]:
            if ans[j][1] < low:
                low = ans[j][1]
            j += 1
        if low > 10**10:
            pp.append(-1)
        else:
            pp.append(low)
            
    print(*pp)
        
        


from collections import defaultdict

T = int(input())

for t in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]

    els = sorted(set(A))

    pos = defaultdict(list)
    for i, el in enumerate(A):
        pos[el].append(i)

    DMAX = {}
    for el in list(pos.keys()):
        dmax = -1
        arr = [-1] + sorted(pos[el]) + [N]
        for i in range(1, len(arr)):
            dmax = max(dmax, arr[i] - arr[i-1])
        DMAX[el] = dmax

    ci = 0
    answer = []

    for i in range(N-1, -1, -1):
        while ci < len(els) and DMAX[els[ci]] > i+1:
            ci += 1
        if ci >= len(els):
            answer.append(-1)
        else:
            answer.append(els[ci])

    print(' '.join(map(str, answer[::-1])))


t = int(input())

for case in range(t):
    n = int(input())
    a = [int(x) - 1 for x in input().split()]

    last_occ = [-1 for _ in range(n)]
    max_dist = [float('-inf') for _ in range(n)]

    for i, x in enumerate(a):
        max_dist[x] = max(max_dist[x], i - last_occ[x])
        last_occ[x] = i

    for x in a:
        max_dist[x] = max(max_dist[x], n - last_occ[x])
        
    inverted = [float('inf') for _ in range(n)]

    for x in a:
        inverted[max_dist[x] - 1] = min(inverted[max_dist[x] - 1], x)

    best = float('inf')
    for x in inverted:
        if x != float('inf'):
            best = min(x, best)

        if best == float('inf'):
            print(-1, end=' ')
        else:
            print(best + 1, end=' ')

    print()
            


import sys
sys.setrecursionlimit(1000000)

T = int(input())
for _ in range(T):
    n = int(input())
    a = [int(x) - 1 for x in input().split()]
    prev = [-1 for _ in range(n)]
    val = [1 for _ in range(n)]
    for i, x in enumerate(a):
        delta = i - prev[x]
        val[x] = max(val[x], delta)
        prev[x] = i
    for i in range(n):
        val[i] = max(val[i], n - prev[i])
    ans = [-1 for _ in range(n + 1)]
    r = n + 1
    for i in range(n):
        if val[i] < r:
            for j in range(val[i], r):
                ans[j] = i + 1
            r = val[i]
    print(' '.join([str(x) for x in ans[1:]]))


for qq in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    last = [-1] * (n+1)
    dura = [-1] * (n+1)
    for i in range(n):
        dura[a[i]] = max(dura[a[i]], i-last[a[i]]-1)
        last[a[i]] = i
    for i in range(n+1):
        dura[i] = max(dura[i], n-last[i]-1)

    ans = [n+1] * n
    for i in range(n+1):
        if dura[i]==n: continue
        ans[dura[i]] = min(ans[dura[i]], i)
    for i in range(n-1):
        ans[i+1] = min(ans[i+1], ans[i])
    for i in range(n):
        if ans[i]==n+1: ans[i] = -1
    print(*ans)

INF = 10 ** 15


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

    d = {i: 0 for i in arr}
    last = {i: -1 for i in arr}
    for i in range(n):
        if last[arr[i]] == -1:
            d[arr[i]] = max(d[arr[i]], i + 1)
        else:
            d[arr[i]] = max(d[arr[i]], i - last[arr[i]])
        last[arr[i]] = i

    for i in list(last.keys()):
        d[i] = max(d[i], n - last[i])

    # print(d)

    d2 = {}
    for k, v in list(d.items()):
        if v not in d2:
            d2[v] = INF
        d2[v] = min(d2[v], k)

    # print(d2)

    ans = [INF] * n
    for i in range(1, n + 1):
        can = INF
        if i != 1:
            can = ans[i - 2]
        if i in list(d2.keys()):
            can = min(can, d2[i])
        ans[i - 1] = can

    for i in range(n):
        if ans[i] == INF:
            ans[i] = -1

    print(*ans)


import sys
import math
def II():
	return int(sys.stdin.readline())
 
def LI():
	return list(map(int, sys.stdin.readline().split()))
 
def MI():
	return map(int, sys.stdin.readline().split())
 
def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
    n = II()
    a = LI()
    d = [[] for i in range(n+1)]
    d2 = [0]*(n+1)
    dp = [0]*(n+1)
    for i in range(n):
        if d2[a[i]] == 0:
            d2[a[i]] = 1
            d[a[i]].append(i)
            dp[a[i]] = i+1
        else:
            d2[a[i]]+=1
            dp[a[i]] = max(dp[a[i]], i-d[a[i]][-1])
            d[a[i]].append(i)
    for i in range(n):
        dp[a[i]] = max(dp[a[i]], n-d[a[i]][-1])
    ans = [-1]*(n+1)
    temp = -1
    for i in range(n+1):
        if ans[dp[i]] == -1:
            ans[dp[i]] = i
    temp = -1
    for i in range(1,n+1):
        if ans[i]!=-1:
            if temp == -1:
                temp = ans[i]
            elif ans[i]<temp:
                temp = ans[i]
            else:
                ans[i] = temp
        else:
            ans[i] = temp
    print(*ans[1:])

for anynumber in range(int(input())):
    n = int(input())
    l = list(map(int,input().split()))
    d = {}
    for (index, i) in enumerate(l):
        if i not in d.keys():
            d[i] = [index+1,index]
        else:
            d[i] = [max(index-d[i][1], d[i][0]),index]
    for i in d.keys():
        d[i] = max(d[i][0], n-d[i][1])
    ans = [-1 for i in range(n)]
    for i in sorted(d.keys(), reverse=True):
        ans[d[i]-1] = i
    for i in range(1,n):
        if ans[i] == -1:
            ans[i] = ans[i-1]
        elif ans[i-1] != -1:
            if ans[i-1]<ans[i]:
                ans[i] = ans[i-1]
    for i in range(n-1):
        print(ans[i],end=" ")
    print(ans[n-1])

t = int(input())
for i in range(t):
    n = int(input())
    a = [int(x) for x in input().split()]
    dct = {}
    for i in a:
        dct[i] = (-1, 0)
    now = 0
    for i in a:
        dct[i] = [now, max(dct[i][1], now - dct[i][0])]
        now += 1
    for i in dct:
        dct[i] = max(dct[i][1], (n - dct[i][0]))
    a = [(dct[i], i) for i in dct]
    a.sort()
    mini = 1000000000000000
    now = 0
    q = len(a)
    for i in range(1, n + 1):
        while now < q and a[now][0] == i:
            mini = min(mini, a[now][1])
            now += 1
        if mini == 1000000000000000:
            print(-1,end=' ')
        else:
            print(mini,end=' ')
    print()

t = int(input())

for w in range(t):
    n = int(input())
    a = tuple(map(int, input().split()))

    d = {}
    for i, x in enumerate(a):
        if x not in d:
            d[x] = [i + 1, i + 1]
        else:
            d[x] = [i + 1, max(d[x][1], i + 1 - d[x][0])]

    l = len(a) + 1
    for i in d:
        d[i] = max(d[i][1], l - d[i][0])

    z = {}
    for i, x in list(d.items()):
        if x in z:
            if z[x] > i:
                z[x] = i
        else:
            z[x] = i

    q = [-1 for x in range(n)]
    for i, x in list(z.items()):
        q[i - 1] = x

    q1 = []
    m = -1
    for x in q:
        if x == -1:
            q1.append(m)
        else:
            if m != -1:
                m = min(m, x)
            else:
                m = x
            q1.append(m)

    print(' '.join(str(x) for x in q1))


t = int(input())
for _ in range(t):
    n = int(input())
    a = [0] + list(map(int, input().split()))

    period = [0 for i in range(n+1)]
    first = [-1 for i in range(n+1)]
    last = [-1 for i in range(n+1)]
    for i in range(1, len(a)):
        b = a[i]
        if first[b] == -1:
            first[b] = i
            last[b] = i
        else:
            period[b] = max(period[b], i - last[b])
            last[b] = i
    
    for i in range(1, len(period)):
        period[i] = max(period[i], n-last[i]+1)
    
    period = period[1:]
    l = sorted(list(e if e[0] > first[e[1]] else (first[e[1]], e[1]) for e in zip(period, list(range(1, n+1))) if e[0] > 0))

    ans = []
    AA = n+5
    ind = 0
    for i in range(1, n+1):
        if ind < len(l) and l[ind][0] == i:
            AA = min(AA, l[ind][1])
        ans.append(-1 if AA == n+5 else AA)
        while ind < len(l) and l[ind][0] == i:
            ind += 1
            
    print(*ans)