AtCoder 148(2019.12-22) D - Brick Break

Question

AtCoder148(2019.12.22開催)のD問題についての質問です

N個のレンガが横一列に並んでいます。
左からi(1 <= i <= n)番目のレンガには、整数 a_iが書かれています。
あなたはこのうち N−1個以下の任意のレンガを選んで砕くことができます。
その結果、K 個のレンガが残っているとします。このとき、任意の整数 
i (1≤i≤K)について、残っているレンガの中で左から i番目のものに書かれた整数が i
であるとき、すぬけさんは満足します。

すぬけさんが満足するために砕く必要のあるレンガの最小個数を出力してください。もし、どのように砕いてもそれが不可能な場合、代わりに -1 を出力してください。

制約
入力は全て整数である。
1≤N≤200000
1≤a_i≤N

入力
入力は以下の形式で標準入力から与えられる。
N
a_1 a_2 a_3........a_n

出力
すぬけさんが満足するために砕く必要のあるレンガの最小個数を出力せよ。もし、どのように砕いてもそれが不可能な場合、代わりに -1 を出力せよ。

この問題の入出力の例として挙げられているもののうち、以下のような例があったのですが

N=3
a_1=2 a_2=2 a_3=2

この例では入力の時点で2番目のレンガに整数２が描かれているためレンガを叩かずとも条件は満たせるのではないかと思うのですが、問題文には「どのように砕いても条件は満たせないため-1を出力せよ」とあります。

何故この例では出力が-1になるのか、どなたか分かる方がいれば教えていただきたいです。

Answer 1

「任意の整数 i (1≤i≤K)について」の意味を理解されていないようです。
iが1でも2でも…Kでも、iにどのような数を代入しても全て、条件を満たさなければならないという意味です。

Answer 2

「残っているレンガの中で左から i番目のものに書かれた整数が i」なので、「左から1番目」、つまり「残った中で一番左のレンガ」には「1」が書かれている必要があります。つまり、今あるレンガに「1」が無ければ、条件を満たしようがありません。

Answer 3

けんちょんの競プロ精進記録
問題の番号や名前で検索すると解説がヒットすることありますのでご参考までに。

問題概要
長さ N の正の整数からなる数列 a1,a2,…,aN が与えられる。この数列からいくつかの値を取り除くことで、数列が 1,2,3,… となるようにしたい。

取り除くべき個数の最小値を求めよ。どのように取り除いても 1,2,… の形にできないときは -1 を出力せよ。

どのように取り除いても 1,2,… の形にできないときは -1 を出力せよ。

Comments

[yusuke-fusegi]

サイトの紹介までありがとうございます。理解できました。