D. Distinct Numbers
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. For each $$$k$$$ from $$$2$$$ to $$$n$$$, find the maximum distance between two distinct elements within any subarray of length $$$k$$$.

Formally, for each $$$k$$$, we want to find:

$$$$$$\max \{ j - i \mid 1 \le i \lt j \le n, \, j - i \lt k, \, a_i \neq a_j \}$$$$$$

If no such pair of distinct elements exists for a given $$$k$$$, the answer is $$$-1$$$.

Input

The first line contains a single integer $$$n$$$, representing the length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, representing the elements of the array.

  • $$$2 \le n \le 3 \times 10^5$$$
  • $$$1 \le a_i \le 10^9$$$
Output

Output $$$n-1$$$ space-separated integers on a single line. The $$$i$$$-th integer should be the answer for $$$k = i + 1$$$.

Examples
Input
4
1 2 1 2
Output
1 1 3
Input
5
3 3 3 3 3
Output
-1 -1 -1 -1
Input
5
1 2 3 4 5
Output
1 2 3 4