No.1053 ゲーミング棒
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 216
作問者 :
QCFium
/ テスター :
tko919
タグ : / 解いたユーザー数 216
作問者 :
QCFium
/ テスター :
tko919
問題文最終更新日: 2020-05-15 21:47:05
問題文
道端にカラフルな棒が落ちているのを見つけました。左右方向に横たわっているこの棒は十分に細く、$N$個の部分に分かれていて左から$i$番目の部分は色$A_i$で塗られています。
このままでもカラフルですが、より美しくするために「同じ色は、出現するならば全てが一つの区間に連続して現れる」を満たすようにしたいです。
そのため以下の操作を$0$回以上行います。
- 棒を一か所で切断する。できた2つの棒の位置を入れ替えて接合する。(それぞれの棒を反転することはない)
テストデータにおいて制約違反が発覚したため、修正してリジャッジを掛けました。申し訳ありません。(2020/05/15 21:47)
入力
$N$ $A_1\ A_2\ A_3\ \dots\ A_N$
$1 \le N \le 10^5$
$1 \le A_i \le N$
入力は全て整数
出力
条件を満たすことが不可能な場合は-1を出力してください。
そうでない場合条件を満たすために必要な操作回数を出力してください。
サンプル
サンプル1
入力
3 1 2 1
出力
1
例えば一番左の区画の右端で切断して操作することで操作後の棒の色は左から順に$2,1,1$となり条件を満たします。
サンプル2
入力
3 1 2 3
出力
0
そのままでも条件を満たしています。
サンプル3
入力
5 1 2 1 2 1
出力
-1
どう頑張っても条件を満たすことはできません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。