On his trip to Japan, Milan wanted to try his chances at pachinko — a Japanese game that can be likened to a vertical game of pinball. By turning a knob, you can control the strength at which you shoot small metal balls into the machine. These metal balls fall down columns and bounce off obstacles until they fall into a gate, with the gate into which your ball falls determining your winnings.

Determined to win, Milan inserts a ~1000~ yen note into the machine and begins to play. He roughly figures out how to turn the knob so that he can get the perfect strength to shoot a ball into a column of his choosing. However, he doesn't really understand the expected winnings for each column and at this point, he is choosing random columns to shoot the balls into. In a matter of minutes, his ~1000~ yen investment has turned into a ~1000~ yen loss, and he is unsure of what to do. He wants to go again and try his luck, but he can only spend another 1000 yen. Spend any more, and he won't be able to have drinks later with his friend Paul. Speaking of Paul...

"Hey Paul, come here" says Milan, gesturing to him to come over.

"Yeah what's up?", says Paul.

"So basically, I put in ~1000~ yen as an investment and it didn't work out."

"Ahh I got you. I put in ~1000~ yen but I managed to get a return of ~500~ yen so I think I know a thing or two."

Paul continues to explain the expected winnings of each column, which he had somehow figured out. He also explains that if Milan goes for a specific column, he has a ~50~% chance of getting it into that column, and ~25~% chances of getting it into the columns directly adjacent to the target column. If the column is on the edge, then he has a ~75~% chance of getting it into that column, with a ~25~% chance of getting it into the adjacent column.

Given a sequence of columns and their expected winnings, which column should Milan go for to maximise his winnings?

Input

The first line consists of an integer ~n~ ~(3 \leq n \leq 10^3)~, the number of columns in the pachinko machine. The following line has ~n~ space-separated integers ~x_0, x_1, ..., x_{n-1}~ ~(-10^3 \leq x_i \leq 10^3)~, the expected winnings for each column.

Output

Output the ~0~-indexed column that will yield the highest expected winnings. If there are multiple indices with the same expected winnings, return the smallest index.

Example

Input 1

6
3 -1 2 7 -4 5

Output 1

3

The expected winnings for each column will be calculated as follows:

• Column ~0~: ~(3 \times 0.75) + (-1 \times 0.25) = 2~
• Column ~1~: ~(3 \times 0.25) + (-1 \times 0.5) + (2 \times 0.25) = 0.75~
• Column ~2~: ~(-1 \times 0.25) + (2 \times 0.5) + (7 \times 0.25) = 2.5~
• Column ~3~: ~(2 \times 0.25) + (7 \times 0.5) + (-4 \times 0.25) = 3~
• Column ~4~: ~(7 \times 0.25) + (-4 \times 0.5) + (5 \times 0.25) = 1~
• Column ~5~: ~(-4 \times 0.25) + (5 \times 0.75) = 2.75~

Column ~3~ has the highest expected return of ~3~.