A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array a, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that a−1=an=−∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
The first line contains the size of array n (n≤106). The second line contains **n** integers a0,a1,...an−1. It is known that ∣ai∣≤109 and also that ai=ai+1 for i=0,1,...,n−2.
Print the index of a peak element. If the array contains multiple peaks, return the index to any of the peaks.