問題一覧 > 通常問題

No.3305 Shift Sort

レベル : / AI推定難易度 : 1875 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 43
作問者 : dyktr_06 / テスター : sepa38 Nafmo2
お気に入りにしたユーザー ProblemId : 12395 / 自分の提出
問題文最終更新日: 2025-10-04 18:13:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest MMA Contest 020 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。