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.
The input contains ~10~ test cases. Each test case starts with an integer ~N~ ~(1 \le N \le 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.
3 5 2 4 5 5 2 4 3 3 5 5 4 1 1 1
1 3 2
Note: Only ~3~ cases are shown in this sample.
In the first case, all three mountains have views of the entire range.
In the second case, the first mountain is the highest. However, you can't see the last two mountains from it since the third mountain is in the way. The third mountain has a view of the whole range.
In the third case, the view from the first mountain only contains the second mountain. The second mountain has a view of the whole range.
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org