Rund was busy this weekend preparing her computer graphics project, so she gave Bitar the following task to complete:
Given an array $a$ of $n$ integers, you have to move the elements in the array to $k$ non-empty arrays (each array has a sub-sequence from the main array) such that you maximize the result of ${\sum_{i = 1}^k mex(array[i])}$.
The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array.
For example: the MEX of [2,2,1] is 0 , the MEX of [1,2,0] is 3.
Check the Note for further explanation if needed.
The first line contains two integers $n$ , $k$ where ($1 \le k \le n \le 100000$).
The second line contains n integers $a_1 , $$a_2 , .... , $$a_n$ ($0 \le a_i \le n$).
Print a single integer , the maximum possible value of ${\sum_{i = 1}^k mex(array[i])}$.
One of the possible partitions for the first case : [1 , 0] , [2 , 5 , 1 , 0].
The MEX for the first array is 2 , and the MEX for the second array is 3, so the answer is 2 + 3 = 5.
Input | Output |
---|---|
6 2 1 2 5 0 1 0 Copy
|
5 Copy
|
2 1 1 1 Copy
|
0 Copy
|