分数: 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
您可以通过以下两个操作对其进行升序排序。
- 将开头的术语移到结尾:现在你有 3, 2, 1.
- 反转整个排列:现在你有 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,10,9,8,7,6,5,4,3,2.
- 将开头的术语移到结尾:现在你有 10,9,8,7,6,5,4,3,2,1.
- 反转整个排列:现在你有 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
无需任何操作。