U76006 环上游戏

有 $n$ 个位置首尾相接成一个环，按顺时针方向编号为 $1,2,\ldots,n$。每个位置初始恰好放有一个数，所有数构成 $1\sim n$ 的一个排列。 每经过一秒，每个数都可以独立地选择以下一种动作： - 留在原位置； - 顺时针移动一个位置； - 逆时针移动一个位置。 任意多个数可以同时移动。移动过程中允许出现空位置，也允许多个数暂时位于同一个位置。 你希望在若干秒后，使每个位置重新恰好有一个数，并满足以下两种状态之一： 1. 沿顺时针方向读取得到 $1,2,\ldots,n$ 的某个循环移位； 2. 沿顺时针方向读取得到 $n,n-1,\ldots,1$ 的某个循环移位。 求达到目标状态所需的最少秒数。 “循环移位”表示可以任选目标序列的起点。例如 $n=5$ 时，`3 4 5 1 2` 是第一类目标状态。

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

输出一个整数表示答案。

对于所有数据，$1\le n\le10^6$，且 $a$ 是 $1\sim n$ 的排列。时间限制为 $2$ 秒，内存限制为 $256$ MiB。 | 子任务 | 测试点数 | 分值 | 限制 | | -----: | -------: | ---: | ------------------------------ | | 1 | 3 | 3 | $n\le8$ | | 2 | 5 | 7 | $n\le2000$ | | 3 | 7 | 12 | 初始排列已经是两类目标状态之一 | | 4 | 9 | 18 | $n\le2\times10^5$ | | 5 | 11 | 25 | $n\le5\times10^5$ | | 6 | 13 | 35 | 无额外限制 |