#P12700. [KOI 2022 Round 2] 停车场

[KOI 2022 Round 2] 停车场

题目背景

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

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

题目描述

有一个圆形的停车塔。停车塔上有 NN 个格子,按顺时针方向依次编号为第 1 个格、第 2 个格、……、第 NN 个格。每个格子中都停有一辆车,第 ii 个格子中的车辆编号为 aia_i

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

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

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

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

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

输入格式

第一行包含一个整数 NN

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

输出格式

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

4
1 2 2 1
3
5
3 1 4 5 1
7

提示

约束条件

  • 1N1000001 \leq N \leq 100\,000
  • 1ai10000000001 \leq a_i \leq 1\,000\,000\,000

子任务

  1. (8 分)对于所有的 iiai=1a_i = 1。即,所有车辆编号都为 1。
  2. (9 分)对于所有的 iji \ne j,有 aiaja_i \ne a_j。即,所有车辆编号各不相同。
  3. (10 分)N10N \leq 10
  4. (21 分)N100N \leq 100
  5. (31 分)N1000N \leq 1\,000
  6. (21 分)无额外约束条件