[AdditionalFile3318.zip](file://AdditionalFile3318.zip?type=additional_file)

#3318. 「CCO 2020」赶作业 ddl

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 CCO 2020 Day1 T2「Exercise Deadlines」，翻译者： ShineEternal。

给定一个长度为 $N$ 的序列 $d_i$。

你有一个长度为 $N$ 的序列 $a_i$，初始状态下 $a_i=i$。

你需要每次交换序列 $a_i$ 中相邻的两个数，使得最终满足对于任意的 $1\le i\le n$，均有 $a_i\le d_i$。求出最少需要多少次。

输入格式

输入第一行一个整数 $N$。

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

输出格式

输出最少的交换次数。

样例 1

输入

4
4 4 3 2

输出

3

最优方案之一为 $(1,4,3,2)$，可通过三次交换由 $(1,2,3,4)$ 得到。

样例 2

输入

3
1 1 3

输出

-1

有两个 $1$，$a_i$ 数组中不存在两个 $\le 1$ 的数，故无解。

数据范围与提示

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