「CCO 2020」赶作业 ddl

题目描述

译自 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

输出

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

输入

3
1 1 3

输出

-1

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