#include <iostream>

using namespace std;

struct nod
{
    int val;
    int ind;
};

nod heap[200005];
int frec[200005];
int lung;

inline int fiu_s(int x)
{
    return (2*x);
}

inline int fiu_d(int x)
{
    return (2*x+1);
}

inline int tata(int x)
{
    return (x/2);
}

inline void schimba(int x,int y)
{
    nod aux;
    aux=heap[x];
    heap[x]=heap[y];
    heap[y]=aux;

    int aux2;
    aux2=frec[heap[x].ind];
    frec[heap[x].ind]=frec[heap[y].ind];
    frec[heap[y].ind]=aux2;

}

void urca(int poz)
{
    cout<<"intrat urc"<<endl;
    while(poz!=1)
      if(heap[tata(poz)].val>heap[poz].val)
      {
          schimba(tata(poz),poz);
          poz=tata(poz);
      }
      else
          break;
    cout<<"iesit urc"<<endl;
}

void coboara(int poz)
{
    cout<<"intrat cob"<<endl;

    int minim=1000000005;
    int fiu=-1;

    while(1)
    {
      int minim=1000000005;
      int fiu=-1;
      if(fiu_s(poz)<=lung)
        if(heap[fiu_s(poz)].val<minim)
        {
            minim=heap[fiu_s(poz)].val;
            fiu=fiu_s(poz);
        }

      if(fiu_d(poz)<=lung)
        if(heap[fiu_d(poz)].val<minim)
        {
            minim=heap[fiu_d(poz)].val;
            fiu=fiu_d(poz);
        }

        if(minim==1000000005)
           break;
        else
        {
           schimba(fiu,poz);
           poz=fiu;
        }
    }
      cout<<"iesit cob"<<endl;
}

int cron;

inline void insert(int x)
{
    cout<<"intrat ins"<<endl;
    heap[++lung].val=x;
    heap[lung].ind=cron++;
    frec[cron]=lung;
    urca(lung);
      cout<<"iesit ins"<<endl;
}

void del(int poz)
{
    cout<<"intrat del"<<endl;
   heap[frec[poz]].val=-1;
   coboara(frec[poz]);
   lung--;
    cout<<"iesit del"<<endl;
}

int min()
{
   return heap[1].val;
}

void afis()
{
    cout<<"Afisare: \n"<<endl;
    int i;
    for(i=1;i<=lung;i++)
    {
        cout<<heap[i].val<<' ';
    }
    cout<<'\n';
    for(i=1;i<=lung;i++)
    {
        cout<<heap[i].ind<<' ';
    }
    cout<<'\n';
}

int main()
{
    lung=0;
    cron=1;

    afis();
    insert(4);
    afis();
    insert(7);
    afis();
    insert(9);
    afis();
    cout<<min()<<endl;
    afis();
    insert(2);
    afis();
    del(1);
    afis();
    cout<<min()<<endl;
    afis();
    insert(3);
    afis();
    del(4);
    afis();
    cout<<min()<<endl;
afis();

    return 0;
}