Drawers

Michał has a chest of $n$ drawers in his bedroom. Each drawer is pulled out by some length. He would like to have direct access to every drawer, so that he does not have to pull them out one by one each time.

There is direct access to a given drawer when every drawer above it is pulled out less than it. Michał decided that he will only push drawers in (that is, decrease how far they are pulled out). He wonders what is the minimum number of drawers he must push in so that he has direct access to all of them.

We assume that a drawer pulled out by $0$ cannot be accessed, and that how far a drawer is pulled out must always be an integer.

The first line contains a single integer $n$ ($1 \le n \le 10^6$), the number of drawers. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is how far the $i$-th drawer (counted from the top of the chest) is pulled out.

Print a single integer: the minimum number of drawers Michał must push in so that there is direct access to all of them. If it is impossible, print $-1$.

For example, if the drawers are pulled out by $8, 4, 7, 6, 8$ from top to bottom, pushing in the first and third drawers gives $1, 4, 5, 6, 8$. Now the pull-out length keeps increasing from top to bottom, so every drawer has direct access, and only $2$ drawers were pushed in.