RoAlgo Educational Round #2 | crestere

This was the problem page during the contest. Access the current page here.
Time limit: 0.1s Memory limit: 4MB Input: Output:

Task

The RoAlgo server is nn 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 ii is calculated based on the formula aiai1a_i - a_{i-1}, where aia_i is the number of members from day ii and ai1a_{i-1} is the number of members from dah i1i-1. We will assume that a0=0a_0 = 0, therefore the growth from day 11 is a1a_1.

Input data

The first line contains nn, the number of days since RoAlgo was created. The second line contains nn 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

  • 1n1 0001 \leq n \leq 1 \ 000;
  • 1a1a2an1061 \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 a6a5=12a_6 - a_5 = 12 is the largest such difference.

Log in or sign up to be able to send submissions!