#include <iostream>
#include <stdexcept>


template <typename T>
class Red{

    struct Cvor{
        T element;
        Cvor *veza;
    };

    Cvor *celo;
    void IzbrisiVrh();
    public:
    Red() : celo(nullptr){}
    ~Red(){while(celo != nullptr) IzbrisiVrh();}
    void Dodaj(T x);
    void SkiniSaCela() {
        if(DaLiJePrazan()) throw std::logic_error("Prazan red");
        IzbrisiVrh();
    };
    T DajCelo() const {
        if(DaLiJePrazan()) throw std::logic_error("Prazan red"); 
        return celo->element;};
    bool DaLiJePrazan() const{ return celo == nullptr;};
    int VelicinaReda() const;
    void Ispisi() const;
    
};

template <typename T>
void Red<T>::Dodaj(T x){
    Cvor *novi = new Cvor {x, nullptr};

    if(!celo || x > celo->element) {
        novi -> veza = celo;
        celo = novi;
        return;
    }
    
    auto p = celo;
    
    while(p->veza != nullptr && p->veza->element > x) p = p->veza;

    novi->veza = p->veza;
    p->veza = novi;
}
template <typename T>
void Red<T>::IzbrisiVrh(){

    Cvor *stari = celo;
    celo = celo->veza;
    delete stari;
}
template <typename T>
int Red<T>::VelicinaReda()const{

    int brojac = 0;
    for(auto p = celo; p != nullptr; p = p->veza) brojac ++;

    return brojac;
}
template <typename T>
void Red<T>::Ispisi() const {
    for(auto p = celo; p != nullptr; p = p->veza)
        std::cout << p->element << " ";
    std::cout << std::endl;
}

int main() {
    Red<int> r;

    r.Dodaj(3);
    r.Dodaj(10);
    r.Dodaj(5);
    r.Dodaj(7);
    r.Dodaj(2);

    r.Ispisi(); // 10 7 5 3 2

    std::cout << "Celo: " << r.DajCelo() << std::endl;

    r.SkiniSaCela();

    r.Ispisi(); // 7 5 3 2

    return 0;
}