RoAlgo Educational Round #2 | crestere

Task

The RoAlgo server is $n$ days old and we know how many members it had after every day. Find the day with the largest growth of the number of members, where the growth in day $i$ is calculated based on the formula $a_i - a_{i-1}$, where $a_i$ is the number of members from day $i$ and $a_{i-1}$ is the number of members from dah $i-1$. We will assume that $a_0 = 0$, therefore the growth from day $1$ is $a_1$.

Input data

The first line contains $n$, the number of days since RoAlgo was created. The second line contains $n$ numbers, representing the number of members of the RoAlgo server. It is guaranteed that the numbers from the array are in non-decreasing order.

Output data

The first line contains the day with the largest increase in the growth of number of members. If there are more such days, print the earliest such day.

Constraints and clarifications

• $1 \leq n \leq 1 \ 000$;
• $1 \leq a_1 \leq a_2 \leq \dots \leq a_n \leq 10^6$.

Example

stdin

7
2 8 12 15 22 34 36

stdout

6

Explanation

The greatest growth came in the sixth day, as $a_6 - a_5 = 12$ is the largest such difference.