You are given an array of $n$ integers. For each $i = 1, 2,\dots, n$, your task is to find the subarray ending at index $i$ with the largest average. If there are multiple subarrays with the largest average, you should find the longest one.

Input

The first line has an integer $n$: the size of the array.

The next line has $n$ integers $x_1, x_2,\dots, x_n$: the contents of the array.

Output

Print $n$ integers: the length of the subarray ending at index $i$ with the largest average for each $i = 1, 2,\dots, n$.

Constraints

• $1 \le n \le 2 \cdot 10^5$
• $1 \le x_i \le 10^6$

Example

Input:

7
1 6 4 6 2 5 5

Output:

1 1 2 1 4 1 2

Explanation: Consider $i = 5$. The averages of all subarrays ending at index $5$ are $\frac{1 + 6 + 4 + 6 + 2}{5} = 3.8$, $\frac{6 + 4 + 6 + 2}{4} = 4.5$, $\frac{4 + 6 + 2}{3} = 4$, $\frac{6 + 2}{2} = 4$ and $\frac{2}{1} = 2$. The largest average is $4.5$ and the length of the corresponding subarray is $4$.