题目描述

小 $A$ 在某一天批发了一些桃子。当天晚上他在做梦时，梦里有位神仙告诉了他此后 $n$ 天内每一天桃子的售价，小 $A$ 万分激动。求：小 $A$ 选择在第几天卖出这些桃子，可以获得的利润最大？

输入格式

第一行：一个整数 $n$，含义与题目中相同。

第二行：$n$ 个整数 $a_1,a_1...a_n$，分别表示每天桃子的售价。

输出格式

输出一个整数 $k$，表示在第 $k$ 天卖出全部桃子获得的利润最大。如果有多个答案，则输出其中的最小值。

样例

6
90 110 95 140 135 140

4

数据规模与约束

对于所有数据，$2≤n≤10^6,1≤x,a_i≤10^6$。