No.3305 Shift Sort
Problem Statement
We define the [ Problem ] for a sequence $B$ as follows.
[ Problem ]
You may perform the following operation any number of times.
- Choose a pair of integers $(l, r)$ satisfying $1 \leq l < r \leq | B |$, and replace $(B_l, \ldots, B_{r-1}, B_r)$ with $(B_r, B_l, \ldots, B_{r-1})$.
Find the minimum number of operations required to sort $B$ in ascending order.
Now, you are given a permutation $A = (A_1, A_2, \ldots, A_N)$ of $(1, 2, \ldots, N)$.
You are given $Q$ queries; process them in order. The $i$-th query is as follows.
l r: Solve the [ Problem ] for the sequence $(A_l, A_{l+1}, \ldots, A_r)$ and output its answer.
Constraints
- $1 \leq N, Q \leq 2 \times 10^{5}$
- $1 \leq A_i \leq N$
- $i \neq j \implies A_i \neq A_j$
- $1 \leq l \leq r \leq N$
- All input values are integers.
Input
The input is given from Standard Input in the following format.
$N$ $Q$ $A_1$ $A_2$ $\cdots$ $A_N$ query $1$ query $2$ $\vdots$ query $Q$
Each query is given in the following format.
l r
Output
Output $Q$ lines.
On the $i$-th line, output the answer to the $i$-th query.
Sample
Sample 1
Input
5 4 4 2 3 1 5 1 3 1 4 2 5 5 5
Output
2 3 1 0
Consider the $2$-nd query.
$(A_1, A_2, A_3, A_4) = (4, 2, 3, 1)$ can be sorted in ascending order by performing the operations as follows.
- Choose $(1, 4)$. $(4, 2, 3, 1)$ is replaced with $(1, 4, 2, 3)$.
- Choose $(2, 4)$. $(1, 4, 2, 3)$ is replaced with $(1, 3, 4, 2)$.
- Choose $(2, 4)$. $(1, 3, 4, 2)$ is replaced with $(1, 2, 3, 4)$.
It is impossible to sort it in ascending order in fewer than $3$ operations, so output $3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
sepa38