#include <iostream>
using namespace std;

const int max_size = 1000;
struct magacin {
    int idx, niza[max_size];
    void init() {
        idx = -1;
    }
    bool isEmpty() {
        if(idx == -1) {
            return true;
        }
        return false;
    }
    bool isFull() {
        if(idx == max_size - 1) {
            return true;
        }
        return false;
    }
    void push(int x) {
        if(isFull()) {
            cout << "Stekot e full" << endl;
            return;
        }
        idx++;
        niza[idx] = x;
    }
    int pop() {
        if(isEmpty()) {
            cout << "Prazen stek" << endl;
            exit(0);
        }

        return niza[idx--];
    }
    int top() {
        if(isEmpty()) {
            cout << "prazen stek" << endl;
            exit(0);
        }
        return niza[idx];
    }
};

struct node {
    int val;
    node *next, *prev;
};

struct DoublyLinkedList  {
    node *head, *tail;

    void init() {
        head = NULL;
        tail = NULL;
    }
    void dodadiPrv(int x) {
        node *tmp = new node;
        tmp->val = x;
        if(head == NULL) {
            head = tmp;
            tail = head;
        }
        else {
            tmp->next = head;
            head->prev = tmp;
            head = tmp;
        }
    }
    void dodadiPosleden(int x) {
        node *tmp = new node;
        tmp->val = x;
        if(head == NULL) {
            head = tmp;
            tail = head;
        }
        else {
            tail->next = tmp;
            tmp->prev = tail;
            tail = tmp;
        }
    }
    void brishiPrv() {
        if(head->next == NULL) {
            delete head;
            head = NULL;
            tail = NULL;
        }
        if(head != NULL) {
            node *tmp = head;
            head = head->next;
            delete tmp;
        }
    }
    void brishiPosleden() {
        if(head->next == NULL) {
            delete head;
            head = NULL;
            tail = NULL;
        }
        else {
            node *tmp = tail;
            tail = tail->prev;
            delete tail;
        }
    }
    void brishiLista() {
        while(head != NULL) {
            brishiPrv();
        }
    }
    void pechati() {
        node *tmp = head;
        while(tmp != NULL) {
            cout << tmp->val << " <--> ";
            tmp = tmp->next;
        }
        cout << endl;
    }
    void dodadiPosle(node * kojNode, int x) {
        node * tmp = new node;
        tmp->val = x;
        if(kojNode == NULL) {
            dodadiPrv(x);
            return;
        }
        if(kojNode->next == NULL) {
            dodadiPosleden(x);
            return;
        }


        node * sleden = kojNode->next;

        kojNode->next = tmp;
        tmp->next = sleden;
        sleden->prev = tmp;
        tmp->prev = kojNode;

    }
    void raspredeliPoBroj(int x) {
        node *tmp = head;
        pechati();

        bool ok = false;
        if(head == NULL) {
            dodadiPrv(x);
            cout << x << " : " << "PRV" << endl;

            return;
        }
        if(x < head->val) {
            dodadiPrv(x);
            cout << x << " : " << "PRV" << endl;

            return;
        }
        while(tmp != NULL) {
            if(x < tmp->val) {
                tmp = tmp->prev;
                break;
            }
            tmp = tmp->next;
        }
        if(tmp == NULL) {
            dodadiPosleden(x);
            cout << x << " : " << "PRV" << endl;

            return;
        }
        cout << x << " : " << tmp->val << endl;
        dodadiPosle(tmp, x);
    }
};

int main()
{
    magacin m;
    m.init();
    m.push(41);
    m.push(41);
    m.push(46);
    m.push(47);
    m.push(44);
    m.push(36);
    m.push(37);
    m.push(36);
    m.push(39);

    DoublyLinkedList maski, zenski;
    maski.init();
    zenski.init();





    while(!m.isEmpty()) {
        int p = m.pop();
        if(p >= 36 && p <= 40) {
            zenski.raspredeliPoBroj(p);
        }
        if(p >= 41 && p <= 47) {
            maski.raspredeliPoBroj(p);
        }
    }
    maski.pechati();
    zenski.pechati();



}