A circular buffer wrote strictly increasing sequence numbers (all distinct) and then wrapped around, so its dump is a strictly increasing sequence rotated left by some unknown amount. For example 1 2 3 4 5 rotated left by 3 becomes 4 5 1 2 3.
Print the minimum value in the list. Solve it in logarithmic time (do not simply scan all values).
Input format
Line 1: an integer n, the number of values.
Line 2: n space-separated distinct integers: the rotated list.
Output format
A single integer: the minimum value.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each value <= 1000000000
- The values are distinct; the list is a rotation of a strictly increasing sequence.