Problem B
Vacation Space
Jón wants to buy a house on a suburbian street. There are $n$ identical houses and they are all available for sale. However, houses are not evenly spaced on the street and Jón wants to be as far as possible from his closest neighbour.
Find the index of the house that is furthest from its closest neighbour. In case of ties, print the earliest house in the input out of the tied houses.
Input
The first line input contains an integer $n$, the number of houses, satisfying $1 \leq n \leq 100\, 000$. Then follow the locations of houses along the street, $n$ integers on the same line, separated by spaces. These locations are all unique, non-negative and at most $10^9$.
Output
Print the index of the house that has the largest minimum distance to a neighbour. If there are ties, print the lowest index among the tied houses. The first house is index $1$, the last index is $n$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 4 3 1 7 11 10 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 9 8 6 4 2 1 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 10 |
1 |
