557. Minimum Element in a Rotated Sorted Array

0

Medium

Given an array of length n that is sorted in ascending order and has been rotated between 1 and n times, find the minimum element in the array. For example, if the original array nums = [0,1,2,4,5,6,7], it might become: [4,5,6,7,0,1,2] after being rotated 4 times.
[0,1,2,4,5,6,7] after being rotated 7 times.
Note that rotating an array [a[0], a[1], a[2], ..., a[n-1]] once results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. You need to write an algorithm that has a time complexity of O(log n).

Input Format

The first line contains the size of the array
The second line contains the elements of the array

Output Format

Print the minimum element as an integer

Example

Input

5 3 4 5 1 2

Output

1

Constraints

n is equal to the length of the array
1 is less than or equal to n and n is less than or equal to 5000
Each element in the array is an integer between -5000 and 5000
All integers in the array are unique
The array is sorted and has been rotated between 1 and n times