A calibration table stores n strictly increasing integers (all distinct). A slot is called self-referential if the value stored at 0-indexed position i equals i.
Print the smallest index i for which a[i] == i, or -1 if no such index exists. Because the values strictly increase, a[i] - i is non-decreasing, so this can be found in logarithmic time.
Input format
Line 1: an integer n, the number of slots.
Line 2: n space-separated integers in strictly increasing order.
Output format
A single integer: the smallest self-referential index, or -1.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each value <= 1000000000
- The values are distinct and strictly increasing.