24275번 - 공정한 동전 스페셜 저지

문제

한별이는 던졌을 때마다 앞면과 뒷면이 나올 확률이 같은 동전 하나를 가지고 있다. 한별이와 히나는 내기를 하는데, 내기는 $N$ 개의 단계로 이루어지며, 올해가 2022ドル$년인 만큼 각 라운드는 동전을 2022ドル$번 던져서 나온 앞면과 뒷면 수를 따라서 게임이 진행된다. $i$ 번째 단계에서 나온 앞면의 수를 $A_i$라고 하자.

히나는 내기에서 져서 한별이의 동전을 의심하기 시작했다. 그래서 한별이의 동전이 앞면과 뒷면이 나올 확률이 같지 않다고 주장하려고 한다. 이 주장에 대한 근거를 마련하려면 우연히 앞면 혹은 뒷면 쪽으로 치우쳐져 나올 확률, 즉 유의확률(p-value)이 낮다는 것을 보여야 한다. 히나는 유의확률을 계산하는 함수 $p(N, K)$를 $N$ 번 동전을 던져서 평균적으로 앞면이 나와야 하는 횟수인 $N/2$와 실제로 앞면이 나온 횟수 $K$가 얼마나 많이 차이가 나는지를 가지고 계산하기로 했다. $N$ 개의 동전을 던져서 $X$ 번 앞면이 나왔다면 평균적으로 앞면이 나와야 하는 횟수인 $N/2$와 $\left|N/2-X\right|$만큼 차이가 난다는 사실을 바탕으로, $p(N, K)$를 앞면과 뒷면이 나올 확률이 같은 동전을 $N$ 번 던졌을 때, 앞면이 나온 횟수와 $N/2$가 $\left|N/2-K\right|$ 이상 차이가 날 확률로 정의하자.

가령이면 동전을 3ドル$번 던져서 앞면이 0ドル$번 나올 확률과 3ドル$번 나올 확률은 1ドル/8,ドル 1ドル$번 나올 확률과 2ドル$번 나올 확률은 3ドル/8$이다. $p(3, 3)$은 3ドル$번 동전을 던졌을 때, 앞면이 나온 횟수와 3ドル/2$가 $\left|3/2-3\right|$ 이상 차이가 날 확률로 정의되고, 이 경우는 앞면이 0ドル$번 나온 경우와 3ドル$번 나온 경우가 해당하기 때문에, $p(3, 3) =1/8+1/8=1/4$이다.

히나는 게임에서 $L$ 번째부터 $R$ 번째까지 단계가 중요하다고 주장하고, 해당 결과를 유의확률을 계산하는 데에 사용하기로 했다. $L$ 번째부터 $R$ 번째 단계까지의 결과만 사용해서 계산된 유의확률은 $p$ 함수의 정의에 따라 $p\left(2022(R-L+1), A_L+\cdots+A_R\right)$로 정의되며, 히나는 이 유의확률로 가능한 최솟값 $\min_{1 \le L \le R \le N} p\left(2022(R-L+1), A_L+\cdots+A_R\right)$를 구하고 싶다.

입력

첫 번째 줄에는 내기의 단계 수 $N$이 주어진다.

두 번째 줄에는 각 라운드에서 앞면이 나온 횟수 $A_1, A_2, \cdots, A_N$ 이 공백으로 구분되어 주어진다.

출력

$\min_{1 \le L \le R \le N} p\left(2022(R-L+1), A_L+\cdots+A_R\right)$를 출력하여라. 정답과의 절대오차는 10ドル^{-6}$ 이하여야 한다.

제한

• 1ドル \le N \le 1\ 000\ 000$
• 0ドル \le A_i \le 2\ 022$
• 입력으로 주어지는 모든 수는 정수이다.

힌트