#include <iostream>
#include <cmath>

using namespace std;

const int N=9;

void heapify_min(int t[], int i, int rozmiar)
{
    int l=2*i;
    int p=2*i+1;
    int najm=i;
    if(l<=rozmiar && t[l]<t[najm]) najm=l;
    if(p<=rozmiar && t[p]<t[najm]) najm=p;
    if(najm!=i)
    {
        swap(t[i], t[najm]);
        heapify_min(t, najm, rozmiar);
    }
}

void build_min_heap(int t[])
{
    int rozmiar=t[0];
    for(int i=rozmiar/2; i>0; i--)
    {
        heapify_min(t, i, rozmiar);
    }
}

void heapify_max(int t[], int i, int rozmiar)
{
    int l=2*i;
    int p=2*i+1;
    int najw=i;
    if(l<=rozmiar && t[l]>t[najw]) najw=l;
    if(p<=rozmiar && t[p]>t[najw]) najw=p;
    if(najw!=i)
    {
        swap(t[i], t[najw]);
        heapify_max(t, najw, rozmiar);
    }
}

void build_max_heap(int t[])
{
    int rozmiar=t[0];
    for(int i=rozmiar/2; i>0; i--)
    {
        heapify_max(t, i, rozmiar);
    }
}

int GetMedian(int heap_max[], int heap_min[])
{
    if(heap_max[0]==heap_min[0])
        return (heap_max[1]+heap_min[1])/2;
    else if(heap_min[0]>heap_max[0]) return heap_min[1];
    else return heap_max[1];
}

void rebalance(int heap_max[], int heap_min[])
{
    if(heap_max[0]>heap_min[0])
    {
        heap_min[0]++;
        swap(heap_max[1], heap_max[heap_max[0]]);
        heap_min[heap_min[0]]=heap_max[heap_max[0]];
        heap_max[heap_max[0]]=0;
        heap_max[0]--;
        heapify_max(heap_max, 1, heap_max[0]);
        int i=heap_min[0];
        while(i/2>0 && heap_min[i]<heap_min[i/2])
        {
            swap(heap_min[i], heap_min[i/2]);
            i/=2;
        }
    }
    else
    {
        heap_max[0]++;
        swap(heap_min[1], heap_min[heap_min[0]]);
        heap_max[heap_max[0]]=heap_min[heap_min[0]];
        heap_min[heap_min[0]]=0;
        heap_min[0]--;
        heapify_min(heap_min, 1, heap_min[0]);
        int i=heap_max[0];
        while(i/2>0 && heap_max[i]>heap_max[i/2])
        {
            swap(heap_max[i], heap_max[i/2]);
            i/=2;
        }
    }
}

void Insert(int k, int heap_max[], int heap_min[])
{
    int m=GetMedian(heap_max, heap_min);
    if(k>m)
    {
        heap_min[0]++;
        heap_min[heap_min[0]]=k;
        int i=heap_min[0];
        while(i/2>0 && heap_min[i]<heap_min[i/2])
        {
            swap(heap_min[i], heap_min[i/2]);
            i/=2;
        }
    }
    else
    {
        heap_max[0]++;
        heap_max[heap_max[0]]=k;
        int i=heap_max[0];
        while(i/2>0 && heap_max[i]>heap_max[i/2])
        {
            swap(heap_max[i], heap_max[i/2]);
            i/=2;
        }
    }
    if(abs(heap_max[0]-heap_min[0])>1) rebalance(heap_max, heap_min);
}

int main()
{
    int t[]={1, 4, 6, 9, 11, 13, 17, 19, 21};
    int heap_max[N]={0};
    for(int i=0; i<N/2; i++)
        heap_max[i+1]=t[i];
    heap_max[0]=N/2;
    build_max_heap(heap_max);
    int heap_min[N]={0};
    for(int i=N/2; i<N; i++)
        heap_min[i-N/2+1]=t[i];
    heap_min[0]=N/2+1;
    build_min_heap(heap_min);
    Insert(2, heap_max, heap_min);
    //for(int i=0; i<N; i++) cout << heap_max[i] << " ";
    cout << GetMedian(heap_max, heap_min);
    return 0;
}