Find Minimum in Rotated Array

Problem statement

A sorted list of distinct sensor readings was rotated by moving an initial prefix to the end. Locate the smallest reading without restoring the whole list. A rotation of zero positions is allowed. Aim for logarithmic running time.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the smallest value.

Constraints

1 <= n <= 100000; values are distinct and between -1000000000 and 1000000000.

Sample input

5
4 8 10 -3 1

Sample output

-3