题目描述

经常跑步的人都知道，匀速跑是最轻松最省力的，如果一下子速度很快，一下子速度又慢下来，这样会加速体力的消耗，不利于长距离跑。同样，徒步也是一样的道理。现在按时间顺序给出小 C 在某次徒步的每个小时的速度，小 C 想你帮忙找出哪一个小时内的速度最接近他走完全程的平均速度。很明显，徒步全程的平均速度=总路程/总时间。

输入格式

共两行：

第一行，一个整数 n ：表示本次徒步一共走了 n 个小时( 1 <= n <= 100000 )。

第二行，有 n 个用空格隔开的整数 $a_i$，表示每个小时的徒步速度（按时间顺序给出，第 1 个是第 1 小时的平均速度、第 2 个是第 2 小时的平均速度、第 3 个是第 3 小时的平均速度......）( 1 <= $a_i$ <= 100000 )

数据范围

对于 50% 的数据：1 ≤ n ≤ 20 , 1 ≤ $a_i$ ≤ 10

对于 90% 的数据：1 ≤ n ≤ 1000 , 1 ≤ $a_i$ ≤ 1000

对于 100% 的数据：1 ≤ n ≤ 100000 , 1 ≤ $a_i$ ≤ 100000

输出格式

一个整数，代表最早出现的最接近总路程的平均速度的那个小时的速度。

样例

6
8 3 5 6 4 7

5

样例解释

本次徒步全程的平均速度是 5.5 公里/小时，其中第 3 小时的 5 公里/小时和第 4 小时的 6 公里每小时都是最接近全程平均速度的，但第 3 小时的 5 公里/小时是最早出现的，因此答案是 5 。