A storage carousel originally held n distinct bin IDs arranged in strictly increasing order. At some point the carousel was rotated by an unknown amount r (0 <= r < n): scanning the current arrangement from the start, you now see the last r original entries followed by the first n - r original entries (a cyclic rotation; r = 0 means no rotation happened).
Given the current (rotated) arrangement of n distinct integers, determine r - equivalently, the 0-indexed position of the smallest value in the arrangement. Print r.
Input format
Line 1: an integer n.
Line 2: n space-separated distinct integers, a rotation of some strictly increasing sequence.
Output format
A single integer: r, the number of positions the carousel was rotated (0 <= r < n).
Constraints
- 1 <= n <= 100000
- all values are distinct
- -1000000000 <= value <= 1000000000