题目描述

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

输出格式

输出最少的交换次数。

4
4 4 3 2

3

3
1 1 3

-1

数据范围与提示

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