3. Mountain View

What is the Problem?

On his trip to the West Coast, Larry has decided to stop by the Rocky Mountains to do some sightseeing.

He only wants to climb one mountain, so he would prefer to climb the mountain with the best view.

The quality of the view is judged by the number of other mountains Larry can see from the peak when

looking either right or left. A mountain is visible from a peak if the straight line connecting the peaks of

the two mountains doesn’t touch any other mountains.

Given the heights of all the mountains in the range, can you figure out which mountain has the best

view? The mountains are all lined up in a straight line and spaced 1 unit apart.

DATA31.txt (DATA32.txt for the second try) will contain 10 test cases. Each test case starts with an

integer N (1 = N = 10,000) indicating the number of mountains. The next line contains N integers ranging

from 1 to 10,000, representing the heights of the mountains in the range. Mountains are numbered

from 1 to N.

For each test case, your program should output an integer corresponding to the mountain with the best

view. If there is a tie, output the smallest numbered mountain.

Sample Input

3

5 2 4

5

5 2 4 3 3

5

5 4 1 1 1

Sample Output

1

3

2

Explanation