Unique Coin Collection

Alice collects coins and wants each coin in her collection to be unique. Sometimes, her collection contains duplicate coins. In one trade, she can exchange one duplicate coin for a coin she does not currently have. Given the total number of coins n, a trade fee parameter t (which does not affect the result in this problem), and a list of n coin values, determine the minimum number of trades Alice must make so that every coin in her collection appears exactly once.

Note: Although a trade fee t is provided, it does not play a role in the calculation.

The problem essentially reduces to counting how many duplicate coins exist in the list.

inputFormat

The input is given via stdin and has the following format:

<n> <t>
<coin1> <coin2> ... <coinn>

Where:

• n: The number of coins.
• t: A trade fee parameter (not used in the computation).
• Next, there are n integers representing the coin values.

outputFormat

The output should be a single integer (printed to stdout) representing the minimum number of trades required so that every coin in the collection is unique.

6 1
1 2 2 3 3 4

2