The Problem

Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}.

If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4!

Input 

Output 

For each input print the current value of the median.

Sample Input 

1
3
4
60
70
50
2

Sample Output 

1
2
3
3
4
27
4

题意有些难读懂。

#include <cstdio>
#include <algorithm>
using std:: sort;
int arr[10002], id;

int main()
{
	int n;
	while(scanf("%d", &n) != EOF){
		arr[id++] = n;
		sort(arr, arr + id);
		
		if(id & 1) printf("%d\n", arr[id / 2]);
		else printf("%d\n", (arr[id / 2] + arr[id / 2 - 1]) / 2);
	}
	return 0;
}