6055: 战争精英
[Creator : ]
Description
小 Z 是一名忠实的游戏爱好者，最近他迷上了一款叫作《战争精英》的第一人称射击类游戏。在这款游戏中，每一局都会由 $1,000$ 名玩家使用各类枪械相互击杀，直到最终剩下唯一的玩家为止。通过没日没夜的练习，小 Z 终于成为了该游戏的高手。
作为小 Z 的小伙伴，小 W 很好奇小 Z 究竟有多厉害。某一天小 W 问小 Z：“你平均每场能够击杀多少人呀？把你最近的战绩给我看看吧。我会在这些击杀数中去掉一个最高的数字，去掉一个最低的数字，最后将剩下的数字取平均数，从而计算出你的平均击杀数。”
小 Z 的手机里记录着他最近的连续 $N$ 场比赛的击杀人数，按时间顺序依次是 $A_1,\ A_2,\ A_3,\ …,\ A_N$，其中 $A_1$ 表示小 Z 刚刚结束的那一局的击杀数，而 $A_N$ 表示小 Z 手机中记录的最早一场的击杀记录。但是小 Z 并没有把这 $N$ 场的战绩都告诉小 W，而是只告诉了小 W 自己最近 $K\ (3≤K≤N)$ 场的战绩，也就是$A_1,\ A_2,\ A_3,\ …,\ A_K$，因为此时小 W 计算出的平均分是最大的。
聪明的你来帮小 Z 算一下，究竟要告诉小 W 最近的多少场游戏的击杀数，才能让小 W 计算的得到的平均击杀数最大呢？如果有多个不同的 $K$ 都能满足小 W 计算的平均击杀数最大，小 Z 会倾向于多给小 W 看一些战绩，因此小 Z 会选择这些 $K$ 中最大的。
Input
第一行一个正整 $N\ (3 \leq N \leq 10^6)$，表示记录了最近 $N$ 场的战绩。
接下来 $N$ 行每行一个正整数，分别表示 $A_1,\ A_2,\ A_3,\ …,\ A_N$。$0 \leq A_i \leq 1,000$
Output
输出一个正整数 $K$。
Sample 1 Input
5
10
6
7
1
8
Sample 1 Output
5
$K=3$ 时平均数为 $7$,
$K=4$ 时平均数为 $6.5$,
$K=5$ 时平均数为 $7$,
按照题意小 Z 会选择平均数最大且 $K$ 尽量大的 $K=5$。