k-Amazing Numbers (Codeforces 1416A)
Tags: Implement, two pointers

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.


Sample Inputs:
3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1

Sample Outputs:
-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    prev = [-1] * (n + 1)
    minLength = [0] * (n + 1)
    for i in range(n):
        val = a[i]
        minLength[val] = max(minLength[val], i - prev[val])
        prev[val] = i
    for val in range(1, n + 1):
        minLength[val] = max(minLength[val], n - prev[val])
    ans = [-1] * (n + 1)
    len_val = n
    for val in range(1, n + 1):
        while len_val >= 1 and len_val >= minLength[val]:
            ans[len_val] = val
            len_val -= 1
    for i in range(1, n + 1):
        print(ans[i], end=' ' if i < n else '\n')

def main():
    t = int(input())
    for _t in range(1, t + 1):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import math
import sys
from typing import List
import heapq

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = [int(x) for x in input().split()]
        d = [-1] * n
        q = [-1] * n
        arr = []
        for (index, r) in enumerate(a):
            r -= 1
            q[r] = max(q[r], index - d[r] - 1)
            d[r] = index
        li = [n + 1] * n
        for index in range(n):
            if d[index] != -1:
                holder = max(q[index], n - d[index] - 1)
                li[holder] = min(li[holder], index + 1)
        lowest = n + 1
        for index in range(n):
            lowest = min(lowest, li[index])
            li[index] = lowest
            if li[index] == n + 1:
                li[index] = -1
        print(*li)
if __name__ == '__main__':
    main()

Solution (Python):
maxn = 300000.0 + 5

def solve(arr, n):
    f = [0] * (n + 1)
    last = [0] * (n + 1)
    ans = [-1] * (n + 1)
    for i in range(1, n + 1):
        x = arr[i]
        f[x] = max(f[x], i - last[x])
        last[x] = i
    for x in range(1, n + 1):
        f[x] = max(f[x], n - last[x] + 1)
        i = f[x]
        while i <= n and ans[i] == -1:
            ans[i] = x
            i += 1
    print(*ans[1:])
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    arr = [0] + arr
    solve(arr, n)
num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()