D - Add to Make a Permutation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます． A の各要素は 0 以上 N-1 以下の整数です．

あなたは以下の操作を 0 回以上行うことができます．

  • A の中からちょうど M 個の要素を選ぶ． そして，選んだ要素の値をそれぞれ 1 増加させる． 増加させたあとに値が N になっている要素があれば，その値を 0 に変更する．

あなたの目標は A を (0,1,\cdots,N-1) の順列にすることです． 目標が達成可能か判定し，可能ならば必要な最小の操作回数を求めてください．

制約

  • 2 \leq N \leq 250000
  • 1 \leq M \leq N-1
  • 0 \leq A_i \leq N-1
  • 入力される値はすべて整数．

入力

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

N M
A_1 A_2 \cdots A_N

出力

目標が達成不可能な場合，-1 を出力せよ． 可能な場合，必要な最小の操作回数を出力せよ．

入力例 1

3 2
0 1 1

出力例 1

2

以下のように操作すると 2 回の操作で目標を達成できます．

  • 初期状態: A=(0,1,1)
  • 1 回目の操作: A_1,A_2 を選んで操作を行い，A=(1,2,1) になる．
  • 2 回目の操作: A_2,A_3 を選んで操作を行い，A=(1,0,2) になる．

2 回未満の操作で目標を達成することはできないため，答えは 2 になります．

入力例 2

5 2
0 4 2 3 1

出力例 2

0

入力例 3

4 2
0 0 1 2

出力例 3

-1

入力例 4

20 15
5 14 18 0 8 5 0 10 6 5 11 2 10 10 17 9 8 14 4 4

出力例 4

10

Score : 700 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N. Each element of A is an integer between 0 and N-1, inclusive.

You can perform the following operation zero or more times:

  • Choose exactly M elements from A. Then, increase the value of each chosen element by 1. Now, if some elements have the values of N, change those values to 0.

Your goal is to make A a permutation of (0,1,\cdots,N-1). Determine if the goal is achievable. If it is, find the minimum number of operations required.

Constraints

  • 2 \leq N \leq 250000
  • 1 \leq M \leq N-1
  • 0 \leq A_i \leq N-1
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \cdots A_N

Output

If the goal is unachievable, print -1. Otherwise, print the minimum number of operations required.

Sample Input 1

3 2
0 1 1

Sample Output 1

2

You can operate as follows to achieve the goal in two operations:

  • Initial state: A=(0,1,1).
  • First operation: Choose A_1 and A_2, making A=(1,2,1).
  • Second operation: Choose A_2 and A_3, making A=(1,0,2).

You cannot achieve the goal in fewer than two operations, so the answer is 2.

Sample Input 2

5 2
0 4 2 3 1

Sample Output 2

0

Sample Input 3

4 2
0 0 1 2

Sample Output 3

-1

Sample Input 4

20 15
5 14 18 0 8 5 0 10 6 5 11 2 10 10 17 9 8 14 4 4

Sample Output 4

10