Find the Peak

Medium#searching #binary-search· solved by 0 · time limit 2.0 s

The array strictly increases up to a single peak and then strictly decreases (either part may be empty). Print the index of the peak in $O(\log n)$ .

Input

$n$ , then $n$ integers.

The 0-based index of the peak.

$1 \le n \le 10^5$

Input

6
1 3 8 12 4 2

Output

Input

3
10 5 1

Output