No.1425 Yet Another Cyclic Shifts Sorting
箱星
first_vilProblem Statement
Koboshi received a sequence $A_1,A_2,\ldots,A_N$ of length $N$ as a birthday present. She wants to sort this sequence in ascending order.
A certain store sells $N-1$ types of tools that perform operations on sequences of length $N$. For $i=2,3,\ldots,N$, tool $i$ performs the following operation on a sequence $B_1,B_2,\ldots,B_N$ of length $N$.
- Perform a cyclic shift on the first $i$ terms. That is, change $B_1,B_2,\ldots,B_i,B_{i+1},\ldots,B_N$ to $B_2,\ldots,B_i,B_1,B_{i+1},\ldots,B_N$.
Koboshi is going to buy $0$ or more types of tools at this store. Each tool she buys can be used any number of times.
What is the minimum number of types of tools needed to sort the sequence $A_1,A_2,\ldots,A_N$ in ascending order?
Input
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
- All inputs are integers.
- $2\le N\le 2\times 10^5$
- $1\le A_i\le 10^9$
Output
Output the minimum number of types of tools needed to sort the sequence in ascending order.
Sample
Sample 1
Input
5 3 4 1 6 7
Output
1
Buy the tool that performs a cyclic shift on the first $3$ terms. Using this tool $1$ time changes the sequence from $3,4,1,6,7$ to $4,1,3,6,7$. Using it $1$ more time changes it to $1,3,4,6,7$, which sorts it in ascending order.
Sample 2
Input
6 5 3 1 2 4 6
Output
2
Performing a cyclic shift on the first $5$ terms changes the sequence to $3,1,2,4,5,6$, and then performing a cyclic shift on the first $3$ terms changes it to $1,2,3,4,5,6$. Thus, the sequence can be sorted in ascending order with $2$ types of tools. It cannot be sorted in ascending order with $1$ or fewer types of tools.
Sample 3
Input
4 1 1 2 3
Output
0
The sequence is already in ascending order from the beginning.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。