今天是 Byteman 的生日。在他的生日派对上有 $n$ 个孩子（包括 Byteman 自己）。孩子们被从 $1$ 到 $n$ 编号。Byteman 的父母准备了一张大圆桌，并在圆桌周围摆放了 $n$ 把椅子。当孩子们到达时，他们依次就座。孩子 $1$ 坐在其中一个座位上。然后孩子 $2$ 坐在他左边的座位上。接着孩子 $3$ 坐在左边的下一个座位上，依此类推。最后，孩子 $n$ 坐在最后一个空位上，也就是孩子 $1$ 和孩子 $n-1$ 之间。

Byteman 的父母非常了解这些孩子，他们知道如果某些孩子坐得太近，他们会变得很吵闹。因此，父母打算让孩子们按特定的顺序重新就座。这样一个顺序可以用一个排列 $p_1, p_2, \dots, p_n$（$p_1, p_2, \dots, p_n$ 是 $1$ 到 $n$ 的互不相同的整数）来描述——孩子 $p_1$ 应该坐在 $p_n$ 和 $p_2$ 之间，孩子 $p_i$（对于 $i = 2, 3, \dots, n-1$）应该坐在 $p_{i-1}$ 和 $p_{i+1}$ 之间，而孩子 $p_n$ 应该坐在 $p_{n-1}$ 和 $p_1$ 之间。请注意，孩子 $p_1$ 可以坐在孩子 $p_n$ 的左侧或右侧。

为了让所有孩子按给定的顺序就座，父母必须让每个孩子沿着圆桌向左或向右移动若干个座位的距离。对于每个孩子，他们必须决定该孩子将如何移动——也就是说，他们必须选择移动的方向（向左或向右）和距离（移动的座位数）。在给定的信号下，所有孩子同时站起来，移动到合适的位置并坐下。

重新就座的过程会使生日派对变得混乱。混乱度等于任何一个孩子移动的最大距离。孩子们可以通过多种方式重新就座。父母希望选择一种使混乱度最小的方案。请帮助他们找到这样一种重新就座的方法。

任务

您的任务是编写一个程序：

• 从标准输入读取孩子的数量以及描述期望孩子顺序的排列，
• 确定最小可能的混乱度，
• 将结果写入标准输出。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 1\,000\,000$）。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，用单个空格分隔。数字 $p_1, p_2, \dots, p_n$ 构成集合 $\{1, 2, \dots, n\}$ 的一个排列，描述了期望的孩子顺序。

此外，在 $50\%$ 的测试数据中，$n$ 将不超过 $1\,000$。

输出格式

输出的第一行也是唯一的一行应该包含一个整数：最小可能的混乱度。

样例

输入样例 1

6
3 4 5 1 2 6

输出样例 1

2

说明

左图显示了孩子们的初始排列。中间的图显示了以下重新就座方案的结果：孩子 $1$ 和 $2$ 移动一个位置，孩子 $3$ 和 $5$ 移动两个位置，孩子 $4$ 和 $6$ 保持原位。此时满足了排列条件，因为 $3$ 坐在 $6$ 和 $4$ 之间，$4$ 坐在 $3$ 和 $5$ 之间，$5$ 坐在 $4$ 和 $1$ 之间，$1$ 坐在 $5$ 和 $2$ 之间，$2$ 坐在 $1$ 和 $6$ 之间，而 $6$ 坐在 $2$ 和 $3$ 之间。

还存在另一种可能的最终排列，如右图所示。在这两种情况下，没有一个孩子移动超过两个座位。