← 返回题目列表

AtCoder · arc132_b

B. 换档和反向

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给定是一个排列 p_1,\dots,p_n of 1,\dots,n。 在此排列中,您可以按任意顺序执行任意次数的以下操作。

  • 反转整个排列。也就是重新排列 p_1,p_2,\dots,p_n to p_n,p_{n-1},\dots,p_1.
  • 将开头的术语移至结尾。也就是重新排列 p_1,p_2,\dots,p_n to p_2,\dots, p_n, p_1.

求按升序对排列进行排序所需的最少操作数。 在给定的输入中,保证这些操作可以按升序对排列进行排序。

约束

  • 2 \leq n \leq 10^5
  • p_1,\dots,p_n 是一个排列 1,\dots,n.
  • Problem Statement中的操作可以排序 p_1,\dots,p_n 按升序排列。

输入

输入由标准输入按以下格式给出:

n
p_1 \dots p_n

输出

打印按升序对排列进行排序所需的最少操作数。


示例输入 1

3
1 3 2

示例输出 1

2

您可以通过以下两个操作对其进行升序排序。

  1. 将开头的术语移到结尾:现在你有 3, 2, 1.
  2. 反转整个排列:现在你有 1, 2, 3.

你不能用少于两次的操作对其进行排序,所以答案是 2.


示例输入 2

2
2 1

示例输出 2

1

执行任一操作一次都会按升序对其进行排序。

你不能用少于一次的操作对其进行排序,所以答案是 1.


示例输入 3

10
2 3 4 5 6 7 8 9 10 1

示例输出 3

3

您可以通过以下三个操作将其按升序排序。

  1. 反转整个排列:现在你有 1,10,9,8,7,6,5,4,3,2.
  2. 将开头的术语移到结尾:现在你有 10,9,8,7,6,5,4,3,2,1.
  3. 反转整个排列:现在你有 1,2,3,4,5,6,7,8,9,10.

你不能用少于三个操作对其进行排序,所以答案是 3.


示例输入 4

12
1 2 3 4 5 6 7 8 9 10 11 12

示例输出 4

0

无需任何操作。