Given an array of ‘n’ integers arr. Find the Peak element of the array. The peak element of an array is defined as that element which is greater than both of its neighbours. I.e if arr[i] is the peak element, arr[i-1]<arr[i] and arr[i+1]<arr[i].

It is guaranteed that there exists only one peak element in the array.

Note:

1.Do not print anything, just return the value of peak element of the array.
2.The first element can be the peak element if and only if the array is non-increasing i.e. it will be a peak if its equal to second element.
3.The last element can be the peak element if and only if the array is non decreasing i.e. it will be a peak if it's equal to second last element.
4.Consider 0 based Indexing.

Constraints:

1 <= N <= 10^5
-10^9 <= arr[i] <= 10^9

Where ‘N’ denotes the number of elements in the sequence and arr[i] denotes the ‘i-th’ element of the sequence.

Time limit: 1 second

Sample Input 1:

5
1 2 3 2 1

Sample Output 1:

  3

Explanation of sample input 1 :

In the given array we can see that the peak element is 3 because the element to its left and right is 2 which is less than 3. If we take any other element lets say the element at index 1 which is 2 (0-based indexing) we see the element to its left is 1 which is less but the element to its right is 3 which is not less therefore 2 can not be a peak element of the array.

Sample Input 2:

5
2 3 4 1 -4

Sample Output 2:

4