C. Trivial Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers $$$a_1,a_2,a_3,\ldots,a_n$$$.

Define $$$f(k)$$$ as the $$$\text{MEX}$$$ of the maximum value of all subarrays of length $$$k$$$.

Print $$$f(k)$$$ for each $$$k$$$ from 1 to n.

More formally, output the values of $$$\text{MEX}^{n-i}_{j=0} \max^{i}_{k=1} a_{j+k}$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$.

A subarray of length $$$k$$$ is an array that contains exactly $$$k$$$ elements obtained by removing a prefix and a suffix from the original array.

The $$$\text{MEX}$$$, or minimal excluded, of a sequence is the smallest non-negative integer not present in that sequence.

Input

The first line contains $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the number of elements in the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-6$$$ satisfy $$$n \leq 10^3$$$.

Tests $$$7-8$$$ satisfy $$$a_i=i-1$$$.

Tests $$$9-20$$$ satisfy no additional constraints.

Output

One line containing $$$n$$$ integers, the $$$i$$$-th integer denoting the value of $$$\text{MEX}^{n-i}_{j=0} \max^{i}_{k=1} a_{j+k}$$$ at $$$i$$$.

Example
Input
3
2 1 0
Output
3 0 0
Note

For $$$k=1$$$, the $$$\max$$$ of each subarray is $$${2, 1, 0}$$$, so the $$$\text{MEX}$$$ is $$$3$$$.

For $$$k=2$$$, the $$$\max$$$ of each subarray isare $$${2, 1}$$$, so the $$$\text{MEX}$$$ is $$$0$$$.

For $$$k=3$$$, the $$$\max$$$ of each subarray isare $$${2}$$$, so the $$$\text{MEX}$$$ is $$$0$$$.

—

Problem Idea: culver0412

Problem Preparation: Jasonwei08

Occurrences: Novice H / Advanced C