说明

你是一群生活在二维海洋中的 $n$ 条鲨鱼的领袖。这些鲨鱼从左到右排列，每对相邻鲨鱼之间的距离为一个单位。

作为领袖，你希望所有鲨鱼聚集到一个公共点，形成一个群体。最初，没有两条鲨鱼属于同一个群体；对于每个 $i = 1, \ldots, n$，从左数第 $i$ 条鲨鱼自成一组，其组号为 $a_i$，该组仅包含它自己。

为了实现目标，你可以命令鲨鱼执行 $n - 1$ 次以下操作。

1. 你喊出一个整数 $b$，该整数需同时满足以下条件：
   • 存在一个编号为 $b$ 的组。
   • 存在至少一个编号严格小于 $b$ 的组。
2. 然后，令 $c$ 为严格小于 $b$ 的最大现有组编号，编号为 $b$ 的组中的所有鲨鱼同时移动到编号为 $c$ 的组所在的位置，并且这两个组合并。
3. 合并后的组编号为 $b$，编号为 $c$ 的组不复存在。

所有鲨鱼以每单位时间一个单位距离的恒定速度移动。命令必须顺序执行，执行时间不重叠。一旦一个命令完成，下一个命令可以立即开始。

通过优化地命令鲨鱼 $n - 1$ 次，计算所有鲨鱼聚集到一个公共点所需的最短时间。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 500$）。第二行包含 $n$ 个两两不同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。

输出格式

输出所有鲨鱼聚集到一个公共点所需的最短时间。

4
3 2 4 1

4

9
1 2 4 5 7 8 3 6 9

17

提示

样例输入/输出 #1 的解释

你可以命令鲨鱼执行以下操作：

1. 你喊出 $3$。最左边的鲨鱼移动到左数第二条鲨鱼的位置，它们形成一个编号为 $3$ 的组。这花费 $1$ 单位时间。
2. 你喊出 $4$。右数第二条鲨鱼移动到编号为 $3$ 的组的位置，它们形成一个编号为 $4$ 的组。这花费 $1$ 单位时间。
3. 你喊出 $4$。编号为 $4$ 的组中的鲨鱼移动到最右边位置，形成一个四条鲨鱼的组。这花费 $2$ 单位时间。

总时间为 $1 + 1 + 2 = 4$。可以证明 $4$ 单位时间是最优的。

翻译由 DeepSeek 完成