#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

struct element {
    int broj;
    int brojPonavljanja;
    element* sljedeci;
};

struct elementTip {
    int broj;
    int brojPonavljanja;
};

int main() {
    srand(time(0));
    rand();
    element* lista = NULL;
    element* prosliElement;
    int brojac=0;
    bool pronaden=0;
    int pseudo;
    // upisati pseudoslucajne brojeve u listu
    do {
        pseudo = (rand() % 1000)+1;
        element* trenutni = new element;
        trenutni->sljedeci=NULL;
        trenutni->brojPonavljanja=0;
        trenutni->broj=pseudo;

        if(lista==NULL) {
            lista=trenutni;
            trenutni->brojPonavljanja=1;
        }
        else {
            element* el = lista;
            while(el!=NULL) {
                if(trenutni->broj == el->broj) {
                    pronaden=1;
                    el->brojPonavljanja++;
                }
                el=el->sljedeci;
            }

            if(!pronaden) {
                prosliElement->sljedeci = trenutni;
                trenutni->brojPonavljanja=1;
            }
        }
        if(!pronaden){
            brojac++;
            prosliElement = trenutni;
        }
        pronaden=0;
    }
    while(pseudo != 1000);

    // prekopirat cemo sve elemente u polje radi lakseg sortiranja
    element* el = lista;
    elementTip* elementi = new elementTip[brojac];
    for(int i=0;i<brojac;i++) {
        elementi[i].broj = el->broj;
        elementi[i].brojPonavljanja = el->brojPonavljanja;
        el=el->sljedeci;
    }

    // sort insertion

    for(int i=1;i<brojac;i++) {
        int j=i-1;
        elementTip pom = elementi[i];
        while(j>=0 && elementi[j].brojPonavljanja<pom.brojPonavljanja) {
            elementi[j+1] = elementi[j];
            j--;
        }
        elementi[j+1] = pom;
    }

    // ispisati sve
    for(int i=0;i<brojac;i++) {
        cout << elementi[i].broj << ", " << elementi[i].brojPonavljanja << endl;
    }

    return 0;
}