/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
1,\dots, n の順列 p_1,\dots,p_n が与えられます。 この順列に対して以下の操作を、好きな順で何度でも行えます。
- 全体をひっくりかえす。つまり、p_1,p_2,\dots,p_n を p_n,p_{n-1},\dots,p_1 に並び替える。
- 先頭の項を末尾に移動させる。つまり、p_1, p_2, \dots,p_n を p_2,\dots, p_n, p_1 に並び替える。
順列を昇順に並び替えるのに必要な操作回数の最小値を求めてください。 ただし、与えられる入力について、これらの操作によって順列を昇順に並び替えられることが保証されています。
制約
- 2 \leq n \leq 10^5
- p_1,\dots,p_n は 1,\dots,n の順列
- 問題文中の操作によって p_1,\dots,p_n を昇順に並び替えられる
入力
入力は以下の形式で標準入力から与えられる。
n p_1 \dots p_n
出力
順列を昇順に並び替えるのに必要な操作回数の最小値を出力せよ。
入力例 1
3 1 3 2
出力例 1
2
次のように操作すると 2 回で昇順に並び替えできます。
- 先頭の項を末尾に移動させ、 3, 2, 1 に並び替える。
- 全体をひっくりかえし、1, 2, 3 に並び替える。
2 回未満の操作で昇順に並び替えることはできないため、答えは 2 です。
入力例 2
2 2 1
出力例 2
1
どちらの操作をしても 1 回で昇順に並び替えできます。
1 回未満の操作で昇順に並び替えることはできないため、答えは 1 です。
入力例 3
10 2 3 4 5 6 7 8 9 10 1
出力例 3
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 回未満の操作で昇順に並び替えることはできないため、答えは 3 です。
入力例 4
12 1 2 3 4 5 6 7 8 9 10 11 12
出力例 4
0
一度も操作する必要がありません。
Score : 400 points
Problem Statement
Given is a permutation p_1,\dots,p_n of 1,\dots,n. On this permutation, you can do the operations below any number of times in any order.
- Reverse the entire permutation. That is, rearrange p_1,p_2,\dots,p_n to p_n,p_{n-1},\dots,p_1.
- Move the term at the beginning to the end. That is, rearrange p_1,p_2,\dots,p_n to p_2,\dots, p_n, p_1.
Find the minimum number of operations needed to sort the permutation in ascending order. In the given input, it is guaranteed that these operations can sort the permutation in ascending order.
Constraints
- 2 \leq n \leq 10^5
- p_1,\dots,p_n is a permutation of 1,\dots,n.
- The operations in Problem Statement can sort p_1,\dots,p_n in ascending order.
Input
Input is given from Standard Input in the following format:
n p_1 \dots p_n
Output
Print the minimum number of operations needed to sort the permutation in ascending order.
Sample Input 1
3 1 3 2
Sample Output 1
2
You can sort it in ascending order in two operations as follows.
- Move the term at the beginning to the end: now you have 3, 2, 1.
- Reverse the whole permutation: now you have 1, 2, 3.
You cannot sort it in less than two operations, so the answer is 2.
Sample Input 2
2 2 1
Sample Output 2
1
Doing either operation once will sort it in ascending order.
You cannot sort it in less than one operation, so the answer is 1.
Sample Input 3
10 2 3 4 5 6 7 8 9 10 1
Sample Output 3
3
You can sort it in ascending order in three operations as follows.
- Reverse the whole permutation: now you have 1,10,9,8,7,6,5,4,3,2.
- Move the term at the beginning to the end: now you have 10,9,8,7,6,5,4,3,2,1.
- Reverse the whole permutation: now you have 1,2,3,4,5,6,7,8,9,10.
You cannot sort it in less than three operations, so the answer is 3.
Sample Input 4
12 1 2 3 4 5 6 7 8 9 10 11 12
Sample Output 4
0
No operation is needed.