問題一覧 > 通常問題

No.2304 Distinct Elements

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : Shirotsume / テスター : hamamu 👑 ygussany
2 ProblemId : 9478 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-03 01:28:50

問題文

長さ NN の数列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) が与えられます．あなたは，この数列に対し以下の操作を好きな回数行うことができます．

  • 1≤i≤N1 \leq i \leq N を満たす整数 ii を選ぶ．AiA_i を Ai+1A_i + 1 か Ai−1A_i - 1 のうち好きな方に置き替える．

あなたの目標は，1≤i<j≤N1 \leq i \lt j \leq N を満たす任意の整数対 (i,j)(i, j) について， Ai≠AjA_i \neq A_j である状態にすることです．そのために必要な操作の最小回数を求めてください．

制約

  • 入力は全て整数
  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9

入力

入力は標準入力から以下の形式で与えられる．

NN
A1A_1 A2A_2 …\dots ANA_N

出力

必要な操作の最小回数を出力せよ．

サンプル

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

例えば， (2,2,2)→(1,2,2)→(1,2,3)(2, 2, 2) \rightarrow (1, 2, 2) \rightarrow (1, 2, 3) とすることで， 22 回の操作で目標が達成できます．

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

例えば， (1,2,2,3)→(1,1,2,3)→(0,1,2,3)(1, 2, 2, 3) \rightarrow (1, 1, 2, 3) \rightarrow (0, 1, 2, 3) とすることで， 22 回の操作で目標が達成できます．

操作によって AA の要素が 00 や負になっても構いません．

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

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