k-Amazing Numbers

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≤t≤1000) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1≤n≤3⋅105) — the number of elements in the array. The second line contains n integers a1,a2,…,an (1≤ai≤n) — the elements of the array.

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x7f7f7f7f;
int a[300010];
int last[300010],ans[300010],d[300010];
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n;
    scanf("%d",&n);
    memset(last,0,sizeof(last));
    memset(d,0,sizeof(d));
    memset(a,0,sizeof(a));
    for(int i = 1; i <= n; i++)
    {
      scanf("%d",&a[i]);
      ans[i] = -1;
    }
    for(int i = 1; i <= n; i++)
    {
      d[a[i]] = max(d[a[i]], i - last[a[i]]);
      last[a[i]] = i;
    }
    for(int i = 1; i <= n; i++)
    {
      d[i] = max(d[i], n - last[i] + 1);
      for(int j = d[i]; j <= n && ans[j] == -1; j++) 
        ans[j] = i;
    }
    for(int i = 1; i <= n; i++) printf("%d ",ans[i]);
    printf("\n");
  }
}