有一座圆形停车塔，其中 $N$ 个车位围成一圈。按顺时针方向依次称为第 1、第 2、……、第 $N$ 个车位。每个车位都有一辆车。第 $i$ 个车位中的车的编号为 $a_i$。

停车塔有两个按钮。按下按钮 A 可使停车塔顺时针旋转一个车位，按下按钮 B 则使其逆时针旋转一个车位。下方左图表示上例按下 A 后的状态，右图表示按下 B 后的状态。

现在要将停车塔中的所有车取出。

只能从最下方的一个车位取车。初始时第 1 个车位位于最下方。要取出其他车位中的车，必须先适当按动按钮旋转停车塔，使该车所在车位移到最下方。

此外，要取出编号为 $x$ 的车，必须先取出所有编号小于 $x$ 的车。也就是说，只要塔内还剩下编号小于 $x$ 的车，就不能取出编号为 $x$ 的车。

请编写程序，求出取出所有车所需按动按钮的最少总次数。

数据范围

• $1 \le N \le 100\,000$
• $1 \le a_i \le 1\,000\,000\,000$

子任务

1.（8 分）$a_i=1$（$1\le i\le N$），即所有车的编号均为 1。 2.（9 分）当 $i\ne j$ 时有 $a_i\ne a_j$，即所有车的编号互不相同。 3.（10 分）$N\le10$。 4.（21 分）$N\le100$。 5.（31 分）$N\le1\,000$。 6.（21 分）没有额外限制。

输入格式

第一行给出整数 $N$。

第二行按顺序给出车的编号 $a_1,\ldots,a_N$，用空格分隔。

输出格式

在第一行输出按动按钮的最少总次数。

样例

输入格式 1

4
1 2 2 1

输出格式 1

3

说明

可以按以下顺序操作：取车 → 按钮 A → 取车 → 按钮 A → 取车 → 按钮 A → 取车。

输入格式 2

5
3 1 4 5 1

输出格式 2

7