GFG.java

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class GFG {

    private PriorityQueue<Integer> min = new PriorityQueue<>(), max = new PriorityQueue<>(Comparator.reverseOrder());

    public int findRunningMedian(int a) {
        min.add(a);
        max.add(min.poll());
        if (max.size() - min.size() > 1) {
            min.add(max.poll());
        }
        return (min.size() == max.size()) ? (max.peek() + min.peek()) / 2 : min.peek();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        GFG instance = new GFG();
        while (n-- > 0) {
            int next = sc.nextInt();
            int median = instance.findRunningMedian(next);
            System.out.println(median);
        }
    }

}