問題一覧 > 通常問題

No.1425 Yet Another Cyclic Shifts Sorting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 68
作問者 : 👑 koboshikoboshi / テスター : ir_1st_vilir_1st_vil
16 ProblemId : 5007 / 出題時の順位表
問題文最終更新日: 2021-01-04 13:35:25

問題文

小星さんは誕生日プレゼントとして長さ $N$ の数列 $A_1,A_2,\ldots,A_N$ をもらいました。小星さんはこの数列を昇順にソートしようと思っています。

ある店では長さ $N$ の数列に操作を行う道具が $N-1$ 種類売られています。$i=2,3,\ldots,N$ に対し、道具 $i$ は長さ $N$ の数列 $B_1,B_2,\ldots,B_N$ に次のような操作を行います。

  • 先頭 $i$ 項に巡回シフトを行う。すなわち、$B_1,B_2,\ldots,B_i,B_{i+1},\ldots,B_N$ を $B_2,\ldots,B_i,B_1,B_{i+1},\ldots,B_N$ に変更する。

小星さんはこの店で道具を $0$ 種類以上買おうとしています。買った道具は何回でも使うことができます。

数列 $A_1,A_2,\ldots,A_N$ を昇順にソートするには少なくとも何種類の道具が必要でしょうか。

入力

$N$
$A_1$ $A_2$ $\ldots$ $A_N$
  • 入力はすべて整数
  • $2\le N\le 2\times 10^5$
  • $1\le A_i\le 10^9$

出力

数列を昇順にソートするには少なくとも何種類の道具が必要かを求め、出力してください。

サンプル

サンプル1
入力
5
3 4 1 6 7
出力
1

先頭 $3$ 項に巡回シフトを行う道具を買います。この道具を $1$ 回使うと数列は $3,4,1,6,7$ から $4,1,3,6,7$ になります。もう $1$ 回使うと $1,3,4,6,7$ になり、昇順にソートすることができました。

サンプル2
入力
6
5 3 1 2 4 6
出力
2

先頭 $5$ 項に巡回シフトを行うことで数列は $3,1,2,4,5,6$ になり、さらに先頭 $3$ 項に巡回シフトを行うことで数列は $1,2,3,4,5,6$ になります。よって $2$ 種類の道具で昇順にソートできます。$1$ 種類以下の道具で昇順にソートすることはできません。

サンプル3
入力
4
1 1 2 3
出力
0

はじめから昇順に並んでいます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。