FatGPT's Yogurt Hunt

The statement of this problem is completely written by AI Chat Bot

Once upon a time, a FatGPT-named bot lived in a quaint village full of happiness. FatGPT was an intelligent and responsible bot who lived in house number $0$. There were $N$ lovely houses in this village, numbered from $1$ to $N$, each with its fascination.

One day, Doctor Hard, a knowledgeable local bot, told FatGPT that he should walk daily around the village for improved health. As FatGPT started its daily walks, it observed a curious thing in every house — it contained a certain amount of delicious yogurt, denoted by the value $A_i$. Excited by this newfound discovery, FatGPT set off on a mission to find the house filled with the most yogurt.

However, FatGPT faced a delightful dilemma during its yogurt hunt. It came across situations where multiple houses had the same largest amount of yogurt. In these cases, the intelligent bot had a clever plan — gathering yogurt from the house that was farthest away from its home. The distance between two houses was measured by finding the absolute difference between their house numbers.

As a result of its intense love for yogurt, FatGPT carefully analyzed the yogurt supplies in each residence, considering both the largest amount available and the distance from its own home. It wanted to get the yogurt that would be the tastiest while also taking in the picturesque charm of the area.

Your task is to assist FatGPT in its yogurt hunt by designing a program that determines the house number from which it should collect yogurt.

Input

The first line of input contains a single integer $N$ $(1 \le N \le 10^{5})$— the number of houses.

The second line of input consists of $N$ non-negative integers $A_1,A_2,A_3….,A_N$$(0 \le A_i \le 10^{8})$— the amount of yogurt in each house.

Output

Output a single integer representing the house number from which FatGPT should collect yogurt to maximize its enjoyment. If multiple houses have the same maximum yogurt quantity, choose the house that is farthest away from house number $0$.

Samples

Input	Output
6 4 1 5 2 7 3	5

Input	Output
4 7 122 1 69	2