32136번 - 소신발언

문제

때아닌 한파로 목장에 있던 모든 소의 신발이 언 상태가 되어버렸다! 피돌이는 히터를 하나 설치해서 얼음을 녹이려고 한다.

목장에는 $N$마리의 소가 일렬로 있으며, 이웃한 두 소의 간격은 모두 1ドル$로 동일하다.

히터는 소 한 마리를 골라 그 소가 있는 자리에 설치할 수 있고, 한 번 설치하면 고정되어 움직일 수 없다.

히터를 $i$번 소가 있는 자리에 설치했다고 가정했을 때, $a_j$를 $j$번 소의 신발이 언 정도라고 하면 $j$번 소의 얼음이 녹는 데 걸리는 시간은 $a_j$와 두 소 사이의 거리의 곱, 즉 $D_{ij} = |i-j| \times a_j$이다. (따라서 이 경우 $i$번 소의 얼음은 순식간에 녹게 된다.)

모든 소의 얼음을 녹여야 하므로 히터를 적어도 $T_i = \max_{1 \le j \le n} D_{ij}$의 시간은 가동해야 한다. 피돌이는 히터 가동 시간을 최소화하고자 한다. 히터를 설치할 위치 $i$를 잘 잡아 얻을 수 있는 최소의 $T_i$를 구해보자.

입력

첫째 줄에 $N$이 주어진다. $(2 \le N \le 300\ 000)$

둘째 줄에 $a_1,ドル $a_2,ドル $\dots,ドル $a_N$이 공백으로 구분되어 주어진다. $(1 \le a_i \le 500\ 000)$

출력

첫째 줄에 문제에서 요구하는 $\min_{1 \le i \le n} T_i$를 출력한다.

제한

노트

$|x|$는 실수 $x$의 절댓값으로, $x \ge 0$이면 $x,ドル $x<0$이면 $-x$와 같다.