U76006 环上游戏

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

无

无

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