题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

有一个圆形的停车塔。停车塔上有 $N$ 个格子，按顺时针方向依次编号为第 1 个格、第 2 个格、……、第 $N$ 个格。每个格子中都停有一辆车，第 $i$ 个格子中的车辆编号为 $a_i$。

停车塔上有两个按钮：按下按钮 A 会使整个停车塔顺时针旋转一格，按下按钮 B 会使停车塔逆时针旋转一格。下图左边展示了按下按钮 A 后的状态，右边展示了按下按钮 B 后的状态。

此时，目标是将所有车辆从停车塔中依次取出。

车辆只能从最底部的一个格子被取出。初始时，第 1 个格子位于最底部。要取出不在最底部的车辆，必须先按按钮将其旋转至最底部的位置。

此外，编号为 $x$ 的车辆只能在编号小于 $x$ 的所有车辆都已被取出的情况下才能被取出。换句话说，如果停车塔中还剩下编号小于 $x$ 的车辆，那么编号为 $x$ 的车辆就不能被取出。

请你编写一个程序，计算将所有车辆从停车塔中取出所需按按钮的最少总次数。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，表示每个格子中车辆的编号，按顺时针顺序排列，以空格分隔。

输出格式

输出一个整数，表示将所有车辆从停车塔中取出所需按按钮的最少总次数。

4
1 2 2 1

3

5
3 1 4 5 1

7

提示

约束条件

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

子任务

1. （8 分）对于所有的 $i$，$a_i = 1$。即，所有车辆编号都为 1。
2. （9 分）对于所有的 $i \ne j$，有 $a_i \ne a_j$。即，所有车辆编号各不相同。
3. （10 分）$N \leq 10$
4. （21 分）$N \leq 100$
5. （31 分）$N \leq 1\,000$
6. （21 分）无额外约束条件