Top of a visitor curve

Problem

Hourly visitor counts rise strictly to one highest hour and then fall strictly. Either part can be empty. Print the position (counting from 0) of the highest hour.

Input, output and limits

Input: Line 1: n. Line 2: n visitor counts that strictly rise and then strictly fall.
Output: One integer: the position of the highest count.
Constraints: 1 ≤ n ≤ 10^5
0 ≤ count ≤ 10^9

Examples

Example

Input

6
2 6 9 12 8 3

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

Compare the middle count with the next one. If the next is larger, the top is to the right.

Hint 2

Otherwise the middle could be the top, so keep it with hi = mid.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Find a value in a rotated listmedium
Smallest truck for the parcelsmedium
Smallest value in a rotated listmedium
Slowest speed that clears the queuesmedium
Orders inside a price rangeeasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems