content: //Question--> Find the running median in a stram of numbers passed as an array.
  //median is the middle element in a data set(sorted), if the size of data set is odd 
  //and it is the sum/2 of the two medians in case of even length.
  
  /*Approach--> Here we make use of minheap and maxheap as two buckets which helps
  to maintain the sorted order and get the middle elements.
  Here we need to balance the heaps so that the maximum diff between lengths is <=1*/ 
  
  import java.io.*;
  import java.math.*;
  import java.text.*;
  import java.util.*;
  import java.util.regex.*;
  
  public class Solution {
  
      static double[] runningMedian(int[] a) {
          PriorityQueue<Integer> max=new PriorityQueue<>(Collections.reverseOrder());//on peek gives max
          PriorityQueue<Integer> min=new PriorityQueue<>();//on peek gives min
          double ans[]=new double[a.length];
          for(int i=0;i<a.length;i++){
              int num=a[i];
              addnumber(num,max,min);  //adds the number to one of the two buckets 
              balance(max,min);        //balances the lengths
              if(max.size()>min.size()){
                  ans[i]=(1.0)*max.peek();
              }
              else if(min.size()>max.size()){
                  ans[i]=(1.0)*min.peek();
              }
              else{
                  double v=(max.peek()+min.peek())/2.0;  //in case same lengths
                  ans[i]=v;
              }
          }
          return ans;
          
      }
      static void addnumber(int n,PriorityQueue<Integer> max,PriorityQueue<Integer> min){
         if(max.size()==0||n<max.peek())
         max.add(n);
         else
         min.add(n);
      }
      static void balance(PriorityQueue<Integer> max,PriorityQueue<Integer> min){
          if(Math.abs(max.size()-min.size())>1)
          {
              if(max.size()>min.size()){
                  min.add(max.poll());
              }
              else
              max.add(min.poll());
          }
      }
  
      private static final Scanner scanner = new Scanner(System.in);
  
      public static void main(String[] args) throws IOException {
          BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
  
          int aCount = Integer.parseInt(scanner.nextLine().trim());
  
          int[] a = new int[aCount];
  
          for (int aItr = 0; aItr < aCount; aItr++) {
              int aItem = Integer.parseInt(scanner.nextLine().trim());
              a[aItr] = aItem;
          }
  
          double[] result = runningMedian(a);
  
          for (int resultItr = 0; resultItr < result.length; resultItr++) {
              bufferedWriter.write(String.valueOf(result[resultItr]));
  
              if (resultItr != result.length - 1) {
                  bufferedWriter.write("\n");
              }
          }
  
          bufferedWriter.newLine();
  
          bufferedWriter.close();
      }
  }
  