mediumBinary Search

Find Minimum in Rotated Sorted Array

## Problem

Suppose an array of length `n` sorted in ascending order is **rotated** between `1` and `n` times.

Given the sorted rotated array `nums` of **unique** elements, return the *minimum element* of this array.

You must write an algorithm that runs in `O(log n)` time.

Examples

Input

nums = [3,4,5,1,2]

Output

Original: [1,2,3,4,5], rotated 3 times.

Input

nums = [4,5,6,7,0,1,2]

Output

Original: [0,1,2,4,5,6,7], rotated 4 times.

Input

nums = [11,13,15,17]

Output

Array not really rotated (or rotated n times).

Constraints

n == nums.length 1 <= n <= 5000 -5000 <= nums[i] <= 5000 All the integers of nums are unique. nums is sorted and rotated between 1 and n times.

Python