Find Peak Element

A peak is strictly greater than its neighbors, and the positions beyond both ends of the array count as negative infinity. Adjacent elements are guaranteed to be different. Return the 0-based index of any peak; if there are several peaks, any one of them is correct. O(log n) time is required.

输入格式

The first line contains n (1..1000); the second line contains n integers (−2147483648..2147483647), with adjacent numbers different.

输出格式

Output the 0-based index of any valid peak; it does not have to be the same peak chosen in the example.

样例 1

输入：

4
1 2 3 1

输出：

2

样例 2

输入：

5
1 3 1 3 1

输出：

1

样例 3

输入：

1
-2147483648

输出：

0

样例说明

Example 1: the 3 at index 2 is greater than its neighbors 2 and 1, so the output is 2.

Example 2: the values at indices 1 and 3 are both 3, each strictly greater than the 1s on both sides; outputting either 1 or 3 is accepted.

Example 3: the only element is greater than the positions on both sides, which count as negative infinity, so index 0 is valid even if that element is the smallest 32-bit integer.