#include <iostream>
#include <vector>

using namespace std;

// Functions to calculate the index of the related elements of the
// heap based on the current index.
// We are making these inline to avoid the extra overhead of the
// function-call.  (Generally a good habit for very small functions
// that may be called very frequently.)
inline unsigned int leftChild(unsigned int n) { return 2 * n + 1; }
inline unsigned int rightChild(unsigned int n) { return 2 * n + 2; }
inline unsigned int parent(unsigned int n) { return (n - 1) / 2; }

// PRECONDITION: leftChild(cur) and rightChild(cur) are the roots
//  of valid heaps.
// POSTCONDITION: cur is the root of a valid heap
void heapify(vector<int>& nums, unsigned int cur)
{
  // Just to catch those cases where we are called on a leaf.
  if (nums.size() < leftChild(cur)) return;
  
  // Figure out which child is bigger.  We want to swap with that,
  // since we are doing maxHeaps here.
  int maxChild;
  
  // If we only have 1 child, then it is a left child, and 
  // it is obviously the max.  (We can't have 0 children, that was
  // already dealt with above.)
  if (rightChild(cur) >= nums.size()) 
    maxChild = nums[leftChild(cur)];
  else
    // If we have two, then set maxChild to the max of those two heaps.
    maxChild = max(nums[leftChild(cur)], nums[rightChild(cur)]);

  // If we are bigger than the roots of both heaps, then everything
  // is already heapy.
  if (nums[cur] > maxChild) return;
  
  // If we must swap left, do so.
  if (nums[leftChild(cur)] == maxChild)
    {
      swap(nums[cur], nums[leftChild(cur)]);
      heapify(nums, leftChild(cur));
    }
  // Or go right. 
  else
    {
      swap(nums[cur], nums[rightChild(cur)]);
      heapify(nums, rightChild(cur));
    }
}

// Given an array, build a heap out of it in-place
void buildHeap(vector<int>& nums)
{
  // Start at the first node that has children, since the leaves are 
  // already valid heaps themselves.
  unsigned int cur = parent(nums.size() - 1);
  
  // Call heapify on everything, working up to the root.
  for (unsigned int i = cur + 1; i > 0; i--)
    {
      heapify(nums, i - 1);
    }

  // If you work the math very carefully, you can prove that this is
  // O(n).  It is obviously at least O(n log n), since we are making
  // O(n) calls to heapify which runs in O(log n).
}

// Insert val into the heap
void heapInsert(vector<int>& nums, int val)
{
  // Do the insertion.  ASSUMING there is enough room in our vector,
  // this is O(1).  On those cases where it is O(n), we can still
  // claim it is O(log n) AVERAGE case, as follows:

  // We have to expand O(log n) times when inserting n elements, given
  // that the array doubles at each expansion.  Each expansion takes
  // O(n) time.  Expansion cost: O(n log n) for n insertions. 

  // Each insertion into the heap that doesn't expand takes O(log n),
  // and there are n of them.  Insertion cost O(n log n) for n insertions.
  
  // Therefore, the AVERAGE of n insertions is only O(log n).  But 
  // if you're being real careful, the worst case can actually be O(n)
  // if we are concerned about expansion.
  unsigned int ind = nums.size();

  // Put into the last spot in the heap
  nums.push_back(val);

  // While it needs to bubble up, do so.
  while (nums[ind] > nums[parent(ind)])
    {
      swap(nums[ind], nums[parent(ind)]);
      ind = parent(ind);
    }
}

// Remove the root of the heap
int heapRemove(vector<int>& nums)
{
  // This is what we will return
  int ret = nums[0];
  
  // Now copy the last leaf into the root
  nums[0] = nums[nums.size() - 1];

  // And contract the heap by 1 space
  nums.resize(nums.size() - 1);

  // And then let it bubble down as needed.
  heapify(nums, 0);

  return ret;
}

// Print out the heap
void printHeap(const vector<int>& nums, unsigned int cur, unsigned int depth)
{
  // If we are printing something outside of the heap, stop
  if (cur >= nums.size()) return;

  // Print the structure
  for (unsigned int i = 0; i < depth; i++) cout << " ";
  cout << nums[cur] << endl;

  // Print the children
  printHeap(nums, leftChild(cur), depth + 1);
  printHeap(nums, rightChild(cur), depth + 1);
}

// This works in O(n log n) if you write a proper Heap class that
// contains a vector and keeps track of how much of the vector
// is storing the heap and how much is the sorted list at the end
// of the vector.  As it is, it is O(n log n) but isn't in-place
vector<int> heapSort(vector<int> nums)
{
  // Get a new vector to return
  unsigned int s = nums.size();
  vector<int> ret;
  ret.resize(s);

  // Fill in the vector with heap removals, greatest to least
  for (unsigned int i = 0; i < s; i++)
    {
      ret[s - i - 1] = heapRemove(nums);
    }
  return ret;
}

int main()
{
  vector<int> myHeap;
  int t;
  while (cin >> t)
    {
      myHeap.push_back(t);
    }

  // Now I've got a list of integers that I'd like to build a heap
  // out of
  buildHeap(myHeap);
  printHeap(myHeap, 0, 0);
  cout << endl;

  heapInsert(myHeap, 42);
  printHeap(myHeap, 0, 0);
  cout << endl;

  heapInsert(myHeap, 2);
  printHeap(myHeap, 0, 0);
  cout << endl;

  heapInsert(myHeap, 200);
  printHeap(myHeap, 0, 0);
  cout << endl;

  myHeap = heapSort(myHeap);

  for (unsigned int i = 0; i < myHeap.size(); i++)
    {
      cout << myHeap[i] << endl;
    }
  
}