Description

There are $N$ tasks. Task $i$ must be finished before time $d_i$.

Finishing one task takes only $1$ unit of time.

The current order is $1,2,3\ldots N$, but obviously, this order may fail to finish all tasks.

You may swap any pair of adjacent tasks to make it possible to finish all tasks.

For example: $1,2,3\ldots N\to 1,3,2\ldots N$.

You need to output the minimum number of swaps needed, while ensuring that all tasks can be finished.

If it is impossible to finish all tasks no matter what, output -1.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $d_i$.

Output Format

Output one integer on a single line: the minimum number of swaps needed to ensure all tasks can be finished.

If it is impossible no matter what, output -1.

4
4 4 3 2

3

3
1 1 3

-1

Hint

Sample Explanation

Sample 1 Explanation

One valid order is $1,4,3,2$, which requires $3$ swaps.

Sample 2 Explanation

Obviously, you cannot do two tasks at the same time.

Subtasks

This problem uses bundled testdata.

• Subtask 1 ($68$ points): $N\le 5\times 10^3$.
• Subtask 1 ($32$ points): no special restrictions.

For $100\%$ of the testdata, it is guaranteed that $1\le N\le 2\times 10^5$ and $1\le d_i\le N$.

Notes

This problem is translated from Canadian Computing Olympiad 2020 Day 1 T2 Exercise Deadlines.

Translated by ChatGPT 5