Find Peak Element

Given an array of integers, your task is to find a peak element and return its index. An element is considered a peak if it is strictly greater than its neighbors. For corner elements, we need to consider only one neighbor. It is guaranteed that the array has at least one peak element. The solution must have a logarithmic time complexity.

More formally, given an array \(a\) of size \(n\), find an index \(i\) (0-based) such that:

[ \begin{cases} a[i] > a[i-1] & \text{if } i > 0, \ a[i] > a[i+1] & \text{if } i < n - 1. \end{cases} ]

If there are multiple valid answers, returning any one of them is acceptable.

inputFormat

The first line of input contains a single integer \(n\) denoting the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer, the index of one peak element in the array.

4
1 2 3 1

2