시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 164 54 42 41.584%

문제

길이 N인 수열 A1, A2, ...., An이 주어진다. k = 1, 2, ..., N에 대해 다음을 차례대로 수행하는 프로그램을 작성하시오.

  • Ai에서 시작하는 길이가 k인 구간 Ai, Ai+1, ..., Ai+k-1의 표준편차를 σi라고 할 때, σi가 최대가 되는 i를 출력한다. 만약 그러한 i가 여러 개라면 그 중 가장 작은 i를 출력한다.

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

입력

첫째 줄에 수열의 길이 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에 수열 A1, A2, ...., An이 주어진다. (1 ≤ Ai ≤ 1,000,000, Ai는 정수)

출력

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

예제 입력 1

5
5 4 6 1 10

예제 출력 1

1
4
3
2
1

힌트

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

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

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

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

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