What if a car takes the side of its owner, Kim Pyojun?

A sequence $A_1, A_2, \dots, A_N$ of length $N$ is given. Write a program that does the following for $k = 1, 2, \dots, N$ in order.

• Let $\sigma_i$ be the standard deviation of the length-$k$ interval $A_i, A_{i+1}, \dots, A_{i+k-1}$ starting at $A_i$. Print the $i$ for which $\sigma_i$ is largest. If there are several such $i$, print the smallest one.

For example, if the sequence is $1, 3, 6, 10, 15$ and $k = 2$, the output is $4$, because among intervals of length 2 the one with the largest standard deviation is $10, 15$.

The first line gives the length $N$ of the sequence. ($1 \le N \le 1{,}000$)

The second line gives the sequence $A_1, A_2, \dots, A_N$. ($1 \le A_i \le 1{,}000{,}000$, each $A_i$ is an integer)

Print the value of $i$ for each $k$ over $N$ lines.

For $N$ data values $x_1, x_2, \dots, x_n$,

the mean $m$ is $m = \frac{x_1 + x_2 + \cdots + x_n}{n}$

the variance $V$ is $V = \frac{(x_1 - m)^2 + (x_2 - m)^2 + \cdots + (x_n - m)^2}{n}$

the standard deviation $\sigma$ is $\sigma = \sqrt{V}$.

Shortening "a car takes the side of its owner, Kim Pyojun" to four characters gives "standard deviation." (hehe;; sorry.. lol!!)