题目描述

现在有 $N$ 个任务，第 $i$ 个任务需要在 $d_i$ 的时间前完成。

完成一个任务只需要 $1$ 的时间。

现在的完成顺序为 $1,2,3\ldots N$，但很显然，这种顺序有可能无法完成全部任务。

您可以交换任意相邻的任务序号来达到完成全部任务的结果。

举个例子：$1,2,3\ldots N\to 1,3,2\ldots N$。

您需要在保证所有任务完成的情况下，输出最小的交换次数。

如果无论如何都不能完成所有任务，请输出 -1。

输入格式

第一行为一个整数 $N$。

第二行为 $N$ 个整数 $d_i$。

输出格式

仅一行一个整数，表示在保证所有任务完成的情况下，最小的交换次数。

如果无论如何都不能完成所有任务，请输出 -1。

4
4 4 3 2

3

3
1 1 3

-1

提示

样例解释

样例 1 解释

一种合法的完成顺序为 $1,4,3,2$，需要交换 $3$ 次。

样例 2 解释

很明显，您不可能在同一时间内做完两项任务。

子任务

本题使用捆绑测试

• Subtask 1（$68$ 分）：$N\le 5\times 10^3$。
• Subtask 1（$32$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le N\le 2\times 10^5$，$1\le d_i\le N$。

说明

本题译自 Canadian Computing Olympiad 2020 Day 1 T2 Exercise Deadlines。