题目链接：https://codeforc.es/contest/1417/problem/C
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.
It is guaranteed that the sum of n over all test cases does not exceed 3?105.
Output
For each test case print n integers, where the i-th integer is equal to the i-amazing number of the array.
Example
inputCopy
3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1
outputCopy
-1 -1 3 2 1
-1 4 4 4 2
-1 -1 1 1 1 1
题意
k的范围是 [1, n] ，对于每一个 k ，找出数列在 [1,k],[2,k+1],…[n?k+1,n] 中都出现的数中的最小值。
分析
对于一个 k ，如果一个数存在在每一个子区间里，那么这个数出现的位置 a[i] - a[i - 1] <= k ，并且 a[1] <= k ，n - a[N] <= k 。如果一个数符合 k ，那么它也符合比 k 大的区间。
代码
#include<bits/stdc++.h>
using namespace std;int T;
int n;
int a[300007];
map<int,int> p;
map<int,int> dis;
int ans[300007];
int num[300007],cnt;int main()
{
scanf("%d",&T);while(T--){
memset(ans, 0x3f3f3f3f, sizeof(ans));p.clear();dis.clear();cnt = 0;scanf("%d",&n);for(int i=1;i<=n;i++){
scanf("%d",&a[i]);if(p[a[i]] == 0){
num[++cnt] = a[i];p[a[i]] = i;dis[a[i]] = i;}else{
dis[a[i]] = max(dis[a[i]], i - p[a[i]]);p[a[i]] = i;}}for(int i=1;i<=cnt;i++){
dis[num[i]] = max(dis[num[i]], n - p[num[i]] + 1);ans[dis[num[i]]] = min(ans[dis[num[i]]], num[i]);}int i = 1;while(ans[i] == 0x3f3f3f3f) printf("-1 "), i++;int minn = ans[i];for(i;i<=n;i++){
if(ans[i] < minn) minn = ans[i];else ans[i] = minn;printf("%d ",ans[i]);}printf("\n");}return 0;
}