Cut the Sticks

You are givensticks, where the_length_of each stick is a positive integer. A_cut operation_is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Suppose we have six sticks of the following lengths:

5 4 4 2 2 8

Then, in one_cut operation_we make a cut of length_2_from each of the six sticks. For the next_cut operation_four sticks are left (of non-zero length), whose lengths are the following:

3 2 2 6

The above step is repeated until no sticks are left.

Given the length ofsticks, print the number of sticks that are left before each subsequentcut operations.

Note:_For each_cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).

Input Format The first line contains a single integer. The next line containsintegers:_a0, a1,...aN-1_separated by space, whererepresents the length of thestick.

Output Format For each operation, print the number of sticks that are cut, on separate lines.

Constraints

• Sample Input 0

6
5 4 4 2 2 8

Sample Output 0

6
4
2
1

Sample Input 1

8
1 2 3 4 3 3 2 1

Sample Output 1

8
6
4
1

Explanation

Sample Case 0 :

sticks-length        length-of-cut   sticks-cut
5 4 4 2 2 8             2               6
3 2 2 _ _ 6             2               4
1 _ _ _ _ 4             1               2
_ _ _ _ _ 3             3               1
_ _ _ _ _ _           DONE            DONE

Sample Case 1

sticks-length         length-of-cut   sticks-cut
1 2 3 4 3 3 2 1         1               8
_ 1 2 3 2 2 1 _         1               6
_ _ 1 2 1 1 _ _         1               4
_ _ _ 1 _ _ _ _         1               1
_ _ _ _ _ _ _ _       DONE            DONE

#include <bits/stdc++.h>

using namespace std;

vector <int> cutTheSticks(vector <int> arr) {
    // Complete this function
    vector<int > freq (1001 , 0);
    for(int i = 0; i < arr.size(); i++){
        freq[arr[i]] +=1;
    }
    vector<int> ans; 
    int count = 0;
    for(int i = freq.size() - 1; i >= 0; i--){
        if(freq[i] > 0) {
            count += freq[i];
            ans.push_back(count);
        }
    }
    reverse(ans.begin(), ans.end());

    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int arr_i = 0; arr_i < n; arr_i++){
       cin >> arr[arr_i];
    }
    vector <int> result = cutTheSticks(arr);
    for (ssize_t i = 0; i < result.size(); i++) {
        cout << result[i] << (i != result.size() - 1 ? "\n" : "");
    }
    cout << endl;


    return 0;
}