Implementation: Data Structures


Elon Musk plans to send his spaceships to k different planets. To do this, he has n spaceships. Initially, it is known where each ship will be sent. The planets are numbered from 1 to 109. As SpaceX’s chief space engineer, you are entitled to change the destination of any ship. For the minimum number of changes you need to make sure that all ships are sent to k different planets.


The first line contains two numbers n (1n105) and k (1kn). Second line contains n integers pi (1pi105 ) - the original ship destinations.


Print the minimum number of changes.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 1
1 5 3
Output example #1
Input example #2
5 4
10 1 2 1 10
Output example #2
Author Rafael Sadatimov
Source 2019-2020 Azerbaijan Finals, June 17