공정한 동전

한별이는 던졌을 때마다 앞면과 뒷면이 나올 확률이 같은 동전 하나를 가지고 있다. 한별이와 히나는 내기를 하는데, 내기는 $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$
• 입력으로 주어지는 모든 수는 정수이다.