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

作为领袖，你希望所有鲨鱼聚集在同一个点，形成一个单一的群体。最初，没有两条鲨鱼属于同一个群体；对于每个 $i = 1, \dots, 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, \dots, a_n$ ($1 \le a_i \le n$)。

输出格式

输出所有鲨鱼聚集在同一个点所需的最短时间。

样例

样例输入 1

4
3 2 4 1

样例输出 1

4

说明 1

你可以指挥鲨鱼执行以下操作：

1. 你喊出 3。最左侧的鲨鱼移动到左起第二条鲨鱼的位置，它们形成一个编号为 3 的群体。这需要 1 个单位时间。
2. 你喊出 4。右起第二条鲨鱼移动到编号为 3 的群体所在位置，它们形成一个编号为 4 的群体。这需要 1 个单位时间。
3. 你喊出 4。编号为 4 的群体中的鲨鱼移动到最右侧的位置，形成一个包含四条鲨鱼的群体。这需要 2 个单位时间。

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

样例输入 2

9
1 2 4 5 7 8 3 6 9

样例输出 2

17