{"problem":{"name":"Add to Make a Permutation","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc169_d"},"statements":[{"statement_type":"Markdown","content":"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.\nYou can perform the following operation zero or more times:\n\n*   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$.\n\nYour 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.\n\n## Constraints\n\n*   $2 \\leq N \\leq 250000$\n*   $1 \\leq M \\leq N-1$\n*   $0 \\leq A_i \\leq N-1$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc169_d","tags":[],"sample_group":[["3 2\n0 1 1","2\n\nYou can operate as follows to achieve the goal in two operations:\n\n*   Initial state: $A=(0,1,1)$.\n*   First operation: Choose $A_1$ and $A_2$, making $A=(1,2,1)$.\n*   Second operation: Choose $A_2$ and $A_3$, making $A=(1,0,2)$.\n\nYou cannot achieve the goal in fewer than two operations, so the answer is $2$."],["5 2\n0 4 2 3 1","0"],["4 2\n0 0 1 2","\\-1"],["20 15\n5 14 18 0 8 5 0 10 6 5 11 2 10 10 17 9 8 14 4 4","10"]],"created_at":"2026-03-03 11:01:14"}}