Smallest value in a rotated list

Problem

A sorted list of distinct integers was rotated, so some front part moved to the back, for example 30 40 50 10 20. Print its smallest value without scanning the whole list.

Input, output and limits

Input: Line 1: n. Line 2: the n rotated values (all different).
Output: One integer: the smallest value.
Constraints: 1 ≤ n ≤ 10^5
Values are distinct, -10^9 ≤ value ≤ 10^9

Examples

Example

Input

5
30 40 50 10 20

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

Compare the middle value with the last value of the window. If the middle is larger, the drop is on its right.

Hint 2

If the middle is not larger, it could itself be the smallest, so keep it with hi = mid.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Orders inside a price rangeeasy
Find a value in a rotated listmedium
Smallest bundle that is large enougheasy
Top of a visitor curvemedium
First and last position of a leveleasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems