考虑逆序对和断点的排列分析

Python Hard lists

任务 «考虑逆序对和断点的排列分析»

给定一个从1到n的数字排列。要求判断它是否“几乎恒等”：逆序对的数量（对于i<j且a[i] > a[j]的对）必须等于具有固定断点数的排列可能的最大值。断点是指满足a[k] != k的位置k。如果排列满足条件，则输出断点数量，否则输出-1。此外，如果断点数量为0，则输出0。如果排列不可能（例如，数据不正确），则输出-2。

输入格式

第一行是一个整数 n (1 ≤ n ≤ 10^5)。第二行是 n 个整数 —— 一个排列。

输出格式

一个整数：断点数量、-1 或 -2。

示例

示例 1

输入

abacaba
abacaba

输出

7

示例 2

输入

3
3 2 1

输出

-1

main.py