問題一覧 > 通常問題

No.1053 ゲーミング棒

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 220
作問者 : QCFium / テスター : tko919
11 ProblemId : 4228 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-05-15 21:47:05

問題文

道端にカラフルな棒が落ちているのを見つけました。左右方向に横たわっているこの棒は十分に細く、N個の部分に分かれていて左からi番目の部分は色Aiで塗られています。
このままでもカラフルですが、より美しくするために「同じ色は、出現するならば全てが一つの区間に連続して現れる」を満たすようにしたいです。
そのため以下の操作を0回以上行います。

  • 棒を一か所で切断する。できた2つの棒の位置を入れ替えて接合する。(それぞれの棒を反転することはない)
条件を満たすことはできるでしょうか、できるならば最小で何回の操作で条件を満たすことができるでしょうか。
テストデータにおいて制約違反が発覚したため、修正してリジャッジを掛けました。申し訳ありません。(2020/05/15 21:47)

入力

N
A1 A2 A3 … AN

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