Find the Maximum Element in a Unimodal Array

You are given a unimodal array. An array is called unimodal if it is first strictly increasing and then strictly decreasing. Note that an array may be completely increasing or completely decreasing. Your task is to find and print the maximum element in the array.

Assume the array has at least one element. The goal is to design an algorithm with an expected time complexity of \(O(\log n)\) using a binary search approach.

For example, in the array [1, 3, 8, 12, 4, 2], the maximum element is 12.

inputFormat

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

outputFormat

Output a single integer, which is the maximum element in the array.

## sample

6
1 3 8 12 4 2

12

</p>