样例下载

题目描述

对于一个序列 $a_1, a_2, a_3, ..., a_n$，将最前面的数移动到末尾，就会得到一个新的序列 $a_2, a_3, ..., a_n, a_1$。对新序列不断重复这个操作，一共会得到 n 个序列（包含初始序列）。这些序列被称作循环同构序列。

现在给你 1 ~ n 的一个排列，每次只允许你交换任意两个相邻的元素，问：最少多少次交换可以得到 1, 2, 3, ..., n 的一个循环同构序列？

输入格式

第一行：一个整数 n

接下来 n 行：每行一个数，共 n 个数，表示 1 ~ n 的某个排列

输出格式

一个整数，表示最少的交换次数

样例输入

5 
3 
5 
4 
2 
1

样例输出

2

数据范围

100% 的数据满足 1 ≤ N ≤ 100,000，且数据保证给出的初始排列是 1 ~ n 的一个排列。其中：

有 30% 的数据：N ≤ 10

有 20% 的数据：N = 200

有 20% 的数据：N = 1,000

有 30% 的数据：N = 100,000