A ring log recorded values in non-decreasing order (duplicates allowed) and then wrapped around, so its dump is a non-decreasing sequence rotated left by some unknown amount. For example 0 1 2 2 2 5 7 rotated left by 3 becomes 2 2 5 7 0 1 2.
Print the minimum value in the list. Duplicates make this harder than the distinct case: when the middle and the right endpoint tie, you cannot tell which half holds the minimum and must shrink the search carefully.
Input format
Line 1: an integer n, the number of values.
Line 2: n space-separated integers: the rotated non-decreasing list (duplicates allowed).
Output format
A single integer: the minimum value.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each value <= 1000000000
- The list is a rotation of a non-decreasing sequence (duplicates allowed).