// Arup Guha
// 2/6/2024
// Soluion to COP 3503 Exam 1 Question 2

import java.util.*;

public class rollingmedian {

	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();
		
		// Set up both priority queues.
		PriorityQueue<Integer> left = new PriorityQueue<Integer>(Collections.reverseOrder());
		PriorityQueue<Integer> right = new PriorityQueue<Integer>();
		
		// Loop through the values.
		for (int i=0; i<n; i++) {
		
			// Read it.
			int val = stdin.nextInt();
			
			// Just wanted to deal with this separately.
			if (i == 0) {
				left.offer(val);
				System.out.println(2*val);
				continue;
			}
			
			// If we get here, left always has a value. Here it's safe to go right.
			if (val > left.peek()) 
				right.offer(val);
			
			// Or we can definitely go left.
			else
				left.offer(val);
				
			// Left's too big, even it out.
			if (left.size() > right.size()+1) right.offer(left.poll());
			
			// Right's too big, even it out.
			if (right.size() > left.size()+1) left.offer(right.poll());
			
			// Median is largest value on left.
			if (left.size() > right.size()) System.out.println(2*left.peek());
			
			// Median is smallest on right.
			else if (right.size() > left.size()) System.out.println(2*right.peek());
			
			// Median is average of largest left, smallest right.
			else System.out.println(left.peek()+right.peek());
		}
	}
}