1370: 青春猪头队的绝地救赎

青春猪头ACMer不会梦到怀梦出题人是19级最后一个退役的队伍。

在他们的退役之战46thICPC昆明站中，在比赛的最后一个小时里，他们遇到了一道这样的题：

给一个长度为 $n$ 的数组，请问子数组的平均值最大为多少？

子数组的定义：⼀个或连续多个原数组中的元素组成⼀个新数组(子数组最少包含⼀个元素)。对于数组 $a= \{ 1,2,3 \} $ ， $b= \{1 \}$ 和 $b= \{ 1,2 \}$ 、$b= \{2,3 \}$以及$b=\{1,2,3\}$ 都是 $a$ 的子数组，而 $b=\{1,3\}$不是。

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

第二行包含 $n$ 个整数，代表数组中的数字 $a_i(1 \leq a_i \leq 10^9)$

输出包含一个数字 $k$ ，代表最大的平均值

1
100

100