P6642 [CCO 2020] Exercise Deadlines

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`.

The first line contains an integer $N$. The second line contains $N$ integers $d_i$.

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`.

#### 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](https://cemc.math.uwaterloo.ca/contests/computing/2020/index.html) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day1.pdf) T2 Exercise Deadlines. Translated by ChatGPT 5