1038: Inside the backrooms (hard version)

——简单版本和困难版本的区别在于数据的范围

​ unknown1337最近在一款叫做Inside the backrooms的游戏，游玩过程中他遇到了这样一个谜题：

• 给定一个长度为 $n$ 的数组 $a$，下标从 $1$ 起始。定义区间 $[l, r]$ 的价值为 $(a_l+a_{l+1}+…+a_r)\div(l+r)$ 。求出一个区间，满足该区间的价值最大，并输出该价值。

​ 由于unknown1337正在被窃皮者追杀，他的大脑直接一片空白了，请聪明的你解决谜题，帮助他逃离窃皮者。

第一行一个整数 $n$ ，代表数组的长度 $(1 \leq n \leq 10^5)$。

第二行 $n$ 个整数 ，第 $i$ 个数代表 $a_i$ $(-10^9 \leq a_i \leq 10^9)$ 。

在一行中输出一个小数代表答案，精度为 $1e^{-6}$(请特别注意精度问题)。

6
1 1 -4 5 -1 -4

0.666667