1416A - k-Amazing Numbers - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef map<int, int> mi;
typedef map<ll, ll> ml;
typedef set<int> si;
typedef set<ll> sl;
typedef pair<int, int> pi;
typedef unordered_set<int> uis;
typedef unordered_set<ll> uls;
typedef pair<ll, ll> pl;


#define PA(a, n) for(int i = 0; i < n; i++) cout << a[i] << ' '
#define PV(v) for(auto i : v) cout << i << ' '
#define YES cout << "YES\n"
#define NO cout << "NO\n"


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;

    int a[n];
    map<int, vi> m;

    for(int i = 0; i < n; i++){
      cin >> a[i];
      m[a[i]].push_back(i);
    }

    map<int, int> g;


    for(int i = 1; i <= n; i++){
      if(m.find(i) == m.end()) continue;

      int ms = m[i][0] + 1;
      for(int j = 0; j < m[i].size(); j++){
        if(j == m[i].size() - 1) ms = max(ms, n-m[i][j]);
        else ms = max(ms,m[i][j+1] - m[i][j]);
      }

      if(g.find(ms) == g.end()) g[ms] = i;
      else g[ms] = min(g[ms], i);
    }

    int i = 1;
    while(i <= n && g.find(i) == g.end()){
      cout << -1 << ' ';
      i++;
    }

    int cn = g[i];

    while(i <= n){
      if(g.find(i) == g.end()){
        cout << cn << ' ';
        i++;
        continue;
      }
      else if(g[i] < cn) cn = g[i];
      cout << cn << ' ';
      i++;
    }

    cout << '\n';
  }


  return 0;
}