자동차가 차주 김표준의 편을 들면?

길이 $N$인 수열 $A_1, A_2, \dots, A_N$이 주어진다. $k = 1, 2, \dots, N$에 대해 다음을 차례대로 수행하는 프로그램을 작성하시오.

• $A_i$에서 시작하는 길이가 $k$인 구간 $A_i, A_{i+1}, \dots, A_{i+k-1}$의 표준편차를 $\sigma_i$라고 할 때, $\sigma_i$가 최대가 되는 $i$를 출력한다. 그러한 $i$가 여러 개라면 그중 가장 작은 $i$를 출력한다.

예를 들어, 수열이 $1, 3, 6, 10, 15$이고 $k = 2$라면 $4$를 출력해야 한다. 길이가 2인 구간 중 표준편차가 최대인 구간은 $10, 15$이기 때문이다.

첫째 줄에 수열의 길이 $N$이 주어진다. ($1 \le N \le 1{,}000$)

둘째 줄에 수열 $A_1, A_2, \dots, A_N$이 주어진다. ($1 \le A_i \le 1{,}000{,}000$, $A_i$는 정수)

$N$개의 줄에 걸쳐 각각의 $k$에 대한 $i$의 값을 출력한다.

$N$개의 자료 값 $x_1, x_2, \dots, x_n$이 있을 때,

평균 $m$은 $m = \frac{x_1 + x_2 + \cdots + x_n}{n}$

분산 $V$는 $V = \frac{(x_1 - m)^2 + (x_2 - m)^2 + \cdots + (x_n - m)^2}{n}$

표준편차 $\sigma$는 $\sigma = \sqrt{V}$이다.

"자동차가 차주 김표준의 편을 들다"를 네 글자로 줄이면 "표준편차"이다. (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!)