#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
// Function to group elements of the given array based on first occurrence
// of each element
void rearrange(int A[], int n)
{
// create an empty map to store frequency of each element
// present in the input array
unordered_map<int, int> freq;
vector<int> order;
// traverse the input array and update frequency of each element
for (int i = 0; i < n; i++) {
freq[A[i]]++;
if (std::find(order.begin(), order.end(), A[i]) == order.end())
{
order.push_back(A[i]);
}
}
for (auto & nb : order)
{
for (int i = 0;i < freq[nb];i++)
{
cout << nb << " ";
}
}
}
// main function
int main()
{
int A[] = { 5, 4, 5, 5, 3, 1, 2, 2, 4 };
int n = sizeof(A)/sizeof(A[0]);
rearrange(A, n);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBGdW5jdGlvbiB0byBncm91cCBlbGVtZW50cyBvZiB0aGUgZ2l2ZW4gYXJyYXkgYmFzZWQgb24gZmlyc3Qgb2NjdXJyZW5jZQovLyBvZiBlYWNoIGVsZW1lbnQKdm9pZCByZWFycmFuZ2UoaW50IEFbXSwgaW50IG4pCnsKICAgIC8vIGNyZWF0ZSBhbiBlbXB0eSBtYXAgdG8gc3RvcmUgZnJlcXVlbmN5IG9mIGVhY2ggZWxlbWVudAogICAgLy8gcHJlc2VudCBpbiB0aGUgaW5wdXQgYXJyYXkKICAgIHVub3JkZXJlZF9tYXA8aW50LCBpbnQ+IGZyZXE7CiAgICB2ZWN0b3I8aW50PiBvcmRlcjsKCiAgICAvLyB0cmF2ZXJzZSB0aGUgaW5wdXQgYXJyYXkgYW5kIHVwZGF0ZSBmcmVxdWVuY3kgb2YgZWFjaCBlbGVtZW50CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGZyZXFbQVtpXV0rKzsKCiAgICAgICAgaWYgKHN0ZDo6ZmluZChvcmRlci5iZWdpbigpLCBvcmRlci5lbmQoKSwgQVtpXSkgPT0gb3JkZXIuZW5kKCkpCiAgICAgICAgewogICAgICAgICAgICBvcmRlci5wdXNoX2JhY2soQVtpXSk7CiAgICAgICAgfQogICAgfQoKICAgIGZvciAoYXV0byAmIG5iIDogb3JkZXIpCiAgICB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7aSA8IGZyZXFbbmJdO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQgPDwgbmIgPDwgIiAiOwogICAgICAgIH0KICAgIH0KfQoKLy8gbWFpbiBmdW5jdGlvbgppbnQgbWFpbigpCnsKICAgIGludCBBW10gPSB7IDUsIDQsIDUsIDUsIDMsIDEsIDIsIDIsIDQgfTsKICAgIGludCBuID0gc2l6ZW9mKEEpL3NpemVvZihBWzBdKTsKCiAgICByZWFycmFuZ2UoQSwgbik7CgogICAgcmV0dXJuIDA7Cn0K