U76006 环上游戏

有一个长度为 $n$ 的环，上面的每个位置不重复地放置有 $1...n $ 中的一个整数。每秒我们可以同时让任意多的数沿顺时针或逆时针移动一个位置，这个过程中一个位置可以没有数或有多个数。 请问最少需要多少秒，使得每个位置仍恰好只有一个数，且沿顺时针或逆时针依次为 $1,2,3,...,n$？

输入包含两行。 第一行为一个正整数 $n$。 第二行为 $n$ 个空格隔开的正整数，为一个 $1...n$ 的排列，表示最开始时按顺时针顺序的环上的数。

输出一个整数表示答案。

对于 40% 的数据，$1 \le n \le 3000$ 对于 80% 的数据，$1 \le n \le 3\times 10^5$ 对于 100% 的数据，$1 \le n \le 10^6$