#include <stdio.h>
#include <stdlib.h>
#include <iostream>

#define LMAX 100000

using namespace std;

int maxheap[LMAX], minheap[LMAX];

void maxupdate( int a, int elem ) { /// Pentru inserarea unui elem. intr-un heap maxim
  maxheap[elem] = a; /// Inseram elementul a pe ultima pozitie
  while ( elem > 0 && maxheap[elem] > maxheap[( elem - 1 ) / 2] ) { /// Cat timp mai avem elemente mai mici decat a in heap
    swap( maxheap[elem], maxheap[(elem - 1) / 2] ); /// Il interschimbam
    elem = ( elem - 1 ) / 2;
  }
}

void minupdate( int a, int elem ) { /// Pentru inserarea unui elem. intr-un heap minim
  minheap[elem] = a; /// Inseram elementul a pe ultima pozitie
  while ( elem > 0 && minheap[elem] < minheap[( elem - 1 ) / 2] ) { /// Cat timp mai avem elemente mai mari decat a in heap
    swap( minheap[elem], minheap[(elem - 1) / 2] ); /// Le interschimbam
    elem = ( elem - 1 ) / 2;
  }
}

void minremove( int elem ) { /// Vom scoate primul element din minheap
  int i;
  swap( minheap[0], minheap[elem - 1] ); /// Il interschimbam cu ultimul
  minheap[elem - 1] = 0;
  elem --;
  i = 0;
  while ( i * 2 + 2 < elem
    && ( minheap[i] > minheap[i * 2 + 1] || minheap[i] > minheap[i * 2 + 2]) ) { /// Vom merge pana cand nodul curent nu are 2 copii
    if ( minheap[i * 2 + 1] < minheap[i * 2 + 2] ) { /// Il gasim pe cel mai mic
      swap( minheap[i], minheap[i * 2 + 1] ); /// Si il interschimbam cu poztia la care suntem
      i = i * 2 + 1;
    } else {
      swap( minheap[i], minheap[i * 2 + 2] );
      i = i * 2 + 2;
    }
  }
  if ( i * 2 + 1 < elem && minheap[i] > minheap[i * 2 + 1] ) { /// Daca insa ultimul nod are doar un copil, il interschimbam
    swap( minheap[i], minheap[i * 2 + 1] );
  }
}

void maxremove( int elem ) { /// Vom scoate primul element din maxheap
  int i;
  swap( maxheap[0], maxheap[elem - 1] ); /// Il interschimbam cu ultimul
  maxheap[elem - 1] = 0; /// Nu mai avem nevoie de elementul scos
  elem --;
  i = 0;
  /// Reajustam heapul
  while ( i * 2 + 2 < elem
    && ( maxheap[i] < maxheap[i * 2 + 1] || maxheap[i] < maxheap[i * 2 + 2] ) ) { /// Vom merge pana cand nodul la care suntem nu are doi copii
    if ( maxheap[i * 2 + 1] > maxheap[i * 2 + 2] ) { /// Gasim minimul dintre cei doi copii
      swap( maxheap[i], maxheap[i * 2 + 1] ); /// Il interschimbam cu tatal
      i = i * 2 + 1;
    } else {
      swap( maxheap[i], maxheap[i * 2 + 2] );
      i = i * 2 + 2;
    }
  }
  if ( i * 2 + 1 < elem && maxheap[i] < maxheap[i * 2 + 1] ) { /// Daca ultimul nod are doar un copil, il interschimbam cu tatal
    swap( maxheap[i], maxheap[i * 2 + 1] );
  }
}
void echilibrare( int maxelem, int minelem ) { /// Vom echilibra numarul de elemente din fiecare heap
  int val;
  if ( maxelem - minelem >= 2 ) { /// Daca heapul maxim are cel putin doua elemente in plus fata de hepul minim ( vor fi maxim doua )
    val = maxheap[0]; /// Retinem cea mai mare valoare
    maxremove( maxelem ); /// Si apoi o stergem
    minupdate( val, minelem ); /// Pt a o insera in celalalt heap;
  } else if ( minelem - maxelem >= 2 ) { /// Analog pt situatia inversa
    val = minheap[0];
    minremove( minelem );
    maxupdate( val, maxelem );
  }
}

int main() {
  FILE *fin = fopen( "costume.in", "r" ), *fout = fopen( "costume.out", "w" );
  int n, a, i, minelem, maxelem;
  fscanf( fin, "%d", &n );
  minelem = maxelem = 0; /// Lungimile celor doua heapuri ( la inceput );
  for ( i = 0; i < n; i ++ ) {
    fscanf( fin, "%d", &a );
    if ( a > minheap[0] ) {
      minupdate( a, minelem );
      minelem ++;
    } else {
      maxupdate( a, maxelem );
      maxelem ++;
    }
    if ( minelem - maxelem >= 2 ) {
      echilibrare( maxelem, minelem );
      minelem --;
      maxelem ++;
    } else if ( maxelem - minelem >= 2 ) {
      echilibrare( maxelem, minelem );
      maxelem --;
      minelem ++;
    }
    if ( minelem > maxelem )
      fprintf( fout, "%d ", minheap[0] );
    else {
      fprintf( fout, "%d ", maxheap[0] );
    }
  }
  fclose( fin );
  fclose( fout );
  return 0;
}