AtCoder Regular Contest 132
翻译中…
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.
翻译中…
样例
Input #1
3
1 3 2
Output #1
2
You can sort it in ascending order in two operations as follows.
1. Move the term at the beginning to the end: now you have $3, 2, 1$.
2. Reverse the whole permutation: now you have $1, 2, 3$.
You cannot sort it in less than two operations, so the answer is $2$.
Input #2
2
2 1
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$.
Input #3
10
2 3 4 5 6 7 8 9 10 1
Output #3
3
You can sort it in ascending order in three operations as follows.
1. Reverse the whole permutation: now you have $1,10,9,8,7,6,5,4,3,2$.
2. Move the term at the beginning to the end: now you have $10,9,8,7,6,5,4,3,2,1$.
3. 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$.
Input #4
12
1 2 3 4 5 6 7 8 9 10 11 12
Output #4
0
No operation is needed.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。