Imaxblue has travelled back in time to kill Fuhrer Bradley. Unfortunately, this plan involves infiltrating the Amestris government. This means that he must bribe purchase legal government security cards. There are ~N~ security levels in the Amestris government, numbered ~0~ to ~N-1~. There is a new security card available for purchase at each level, and you can purchase cards at lower levels as well. Initially, Imaxblue has a security level of ~0~, and his total security level is equal to the sum of his cards. Imaxblue would like to raise as little suspicion as possible, by purchasing the most amount of cards before going past the ~(N-1)^\text{th}~ security level. In addition, each card he purchases must have a higher security number than the previous one purchased. Print -1 if it is impossible.

Subtasks

For all cases, ~N \le 200\,000~.
For 5 of the 25 points, ~N \le 4\,000~.

Input Specification

On the first line: ~N~
On the second line: ~N~ integers, representing the security cards available for purchase on the ~i^\text{th}~ day.

Sample Input

9
1 2 5 4 2 3 10 1 1

Sample Output

4

Explanation for Sample Output

First, purchase the card of value ~1~, raising your security level to ~1~.
Then, purchase the card of value ~2~, raising your level to ~3~.
Then, purchase the card of value ~4~, raising your level to ~7~.
Then, purchase the card of value ~5~, raising your level to ~12~.

Note: you cannot purchase the second card of value 2 or the card of value 3, since the cards you purchase must be strictly increasing.