시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 10 9 9 90.000%

문제

Bob has N programming exercises that he needs to complete before their deadlines. Exercise i only takes one time unit to complete, but has a deadline di (1 ≤ di ≤ N) time units from now.

Bob will solve the exercises in an order described by a sequence a1, a2, . . . , aN, such that a1 is the first exercise he solves, a2 is the second exercise he solves, and so on. Bob’s original plan is described by the sequence 1, 2, . . . , N. With one swap operation, Bob can exchange two adjacent numbers in this sequence. What is the minimum number of swaps required to change this sequence into one that completes all exercises on time?

입력

The first line consists of a single integer N (1 ≤ N ≤ 200 000). The next line contains N spaceseparated integers d1, d2, . . . , dN (1 ≤ di ≤ N).

출력

Output a single integer, the minimum number of swaps required for Bob to solve all exercises on time, or -1 if this is impossible.

예제 입력 1

4
4 4 3 2

예제 출력 1

3

One valid sequence is (1, 4, 3, 2), which can be obtained from (1, 2, 3, 4) by three swaps.

예제 입력 2

3
1 1 3

예제 출력 2

-1

There are two exercises that are due at time 1, but only one exercise can be solved by this time.