#include <iostream>
#include <iomanip>
#include <queue>
using std::vector;
using std::greater;
using std::less;
using std::make_heap;
using std::push_heap;
using std::pop_heap;
// Удаляет элемент из min-кучи и возвращает его
int remove_from_min(vector<int>& heap)
{
pop_heap(heap.begin(), heap.end(), greater<int>());
int tmp = heap.back();
heap.pop_back();
return tmp;
}
// Удаляет элемент из max-кучи и возвращает его
int remove_from_max(vector<int>& heap)
{
pop_heap(heap.begin(), heap.end(), less<int>());
int tmp = heap.back();
heap.pop_back();
return tmp;
}
// Добавление нового элемента в min-кучу
void push_to_min(vector<int>& heap, int value)
{
heap.push_back(value);
push_heap(heap.begin(), heap.end(), greater<int>());
}
// Добавление нового элемента в max-кучу
void push_to_max(vector<int>& heap, int value)
{
heap.push_back(value);
push_heap(heap.begin(), heap.end(), less<int>());
}
// Балансирование размеров куч. Если размеры отличаются на 2,
// перекидываем элемент из одной кучи в другую
void balance_heaps(vector<int>& min, vector<int>& max)
{
int tmp;
if(min.size() < max.size())
{
tmp = remove_from_max(max);
push_to_min(min, tmp);
}
if(min.size() > max.size())
{
tmp = remove_from_min(min);
push_to_max(max, tmp);
}
}
// Прочитанный из входного потока элемент добавляется в одну из двух куч.
// При этом производится балансирование размеров
void push_new_value(vector<int>& min, vector<int>& max, int value)
{
push_to_min(min, value);
int diff = min.size() > max.size() ? min.size() - max.size()
: max.size() - min.size();
if(diff == 2)
balance_heaps(min, max);
}
// Вычисление медианы среди всех элементов.
// Если число элементов четное, медиана вычисляется как средне арифметическое
// двух центральных элементов в упорядоченной последовательности
double find_median(vector<int>& min, vector<int>& max)
{
if(min.size() == max.size())
{
pop_heap(min.begin(), min.end(), greater<int>());
pop_heap(max.begin(), max.end(), less<int>());
return (min.back() + max.back()) / 2.0;
}else{
pop_heap(min.begin(), min.end(), greater<int>());
return min.back();
}
}
int main()
{
std::vector<int> min_heap;
std::vector<int> max_heap;
int value;
while(std::cin >> value)
{
push_new_value(min_heap, max_heap, value);
std::cout << std::setprecision(2) << find_median(min_heap, max_heap) << std::endl;
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPHF1ZXVlPgoKdXNpbmcgc3RkOjp2ZWN0b3I7CnVzaW5nIHN0ZDo6Z3JlYXRlcjsKdXNpbmcgc3RkOjpsZXNzOwp1c2luZyBzdGQ6Om1ha2VfaGVhcDsKdXNpbmcgc3RkOjpwdXNoX2hlYXA7CnVzaW5nIHN0ZDo6cG9wX2hlYXA7CgovLyDQo9C00LDQu9GP0LXRgiDRjdC70LXQvNC10L3RgiDQuNC3IG1pbi3QutGD0YfQuCDQuCDQstC+0LfQstGA0LDRidCw0LXRgiDQtdCz0L4KaW50IHJlbW92ZV9mcm9tX21pbih2ZWN0b3I8aW50PiYgaGVhcCkKewoJcG9wX2hlYXAoaGVhcC5iZWdpbigpLCBoZWFwLmVuZCgpLCBncmVhdGVyPGludD4oKSk7CglpbnQgdG1wID0gaGVhcC5iYWNrKCk7CgloZWFwLnBvcF9iYWNrKCk7CglyZXR1cm4gdG1wOwp9CgovLyDQo9C00LDQu9GP0LXRgiDRjdC70LXQvNC10L3RgiDQuNC3IG1heC3QutGD0YfQuCDQuCDQstC+0LfQstGA0LDRidCw0LXRgiDQtdCz0L4KaW50IHJlbW92ZV9mcm9tX21heCh2ZWN0b3I8aW50PiYgaGVhcCkKewoJcG9wX2hlYXAoaGVhcC5iZWdpbigpLCBoZWFwLmVuZCgpLCBsZXNzPGludD4oKSk7CglpbnQgdG1wID0gaGVhcC5iYWNrKCk7CgloZWFwLnBvcF9iYWNrKCk7CglyZXR1cm4gdG1wOwp9CgovLyDQlNC+0LHQsNCy0LvQtdC90LjQtSDQvdC+0LLQvtCz0L4g0Y3Qu9C10LzQtdC90YLQsCDQsiBtaW4t0LrRg9GH0YMKdm9pZCBwdXNoX3RvX21pbih2ZWN0b3I8aW50PiYgaGVhcCwgaW50IHZhbHVlKQp7CgloZWFwLnB1c2hfYmFjayh2YWx1ZSk7CglwdXNoX2hlYXAoaGVhcC5iZWdpbigpLCBoZWFwLmVuZCgpLCBncmVhdGVyPGludD4oKSk7Cn0KCi8vINCU0L7QsdCw0LLQu9C10L3QuNC1INC90L7QstC+0LPQviDRjdC70LXQvNC10L3RgtCwINCyIG1heC3QutGD0YfRgwp2b2lkIHB1c2hfdG9fbWF4KHZlY3RvcjxpbnQ+JiBoZWFwLCBpbnQgdmFsdWUpCnsKCWhlYXAucHVzaF9iYWNrKHZhbHVlKTsKCXB1c2hfaGVhcChoZWFwLmJlZ2luKCksIGhlYXAuZW5kKCksIGxlc3M8aW50PigpKTsKfQoKLy8g0JHQsNC70LDQvdGB0LjRgNC+0LLQsNC90LjQtSDRgNCw0LfQvNC10YDQvtCyINC60YPRhy4g0JXRgdC70Lgg0YDQsNC30LzQtdGA0Ysg0L7RgtC70LjRh9Cw0Y7RgtGB0Y8g0L3QsCAyLAovLyDQv9C10YDQtdC60LjQtNGL0LLQsNC10Lwg0Y3Qu9C10LzQtdC90YIg0LjQtyDQvtC00L3QvtC5INC60YPRh9C4INCyINC00YDRg9Cz0YPRjgp2b2lkIGJhbGFuY2VfaGVhcHModmVjdG9yPGludD4mIG1pbiwgdmVjdG9yPGludD4mIG1heCkKewoJaW50IHRtcDsKCWlmKG1pbi5zaXplKCkgPCBtYXguc2l6ZSgpKQoJewoJCXRtcCA9IHJlbW92ZV9mcm9tX21heChtYXgpOwoJCXB1c2hfdG9fbWluKG1pbiwgdG1wKTsKCX0KCWlmKG1pbi5zaXplKCkgPiBtYXguc2l6ZSgpKQoJewoJCXRtcCA9IHJlbW92ZV9mcm9tX21pbihtaW4pOwoJCXB1c2hfdG9fbWF4KG1heCwgdG1wKTsKCX0KfQoKLy8g0J/RgNC+0YfQuNGC0LDQvdC90YvQuSDQuNC3INCy0YXQvtC00L3QvtCz0L4g0L/QvtGC0L7QutCwINGN0LvQtdC80LXQvdGCINC00L7QsdCw0LLQu9GP0LXRgtGB0Y8g0LIg0L7QtNC90YMg0LjQtyDQtNCy0YPRhSDQutGD0YcuCi8vINCf0YDQuCDRjdGC0L7QvCDQv9GA0L7QuNC30LLQvtC00LjRgtGB0Y8g0LHQsNC70LDQvdGB0LjRgNC+0LLQsNC90LjQtSDRgNCw0LfQvNC10YDQvtCyCnZvaWQgcHVzaF9uZXdfdmFsdWUodmVjdG9yPGludD4mIG1pbiwgdmVjdG9yPGludD4mIG1heCwgaW50IHZhbHVlKQp7CglwdXNoX3RvX21pbihtaW4sIHZhbHVlKTsKCWludCBkaWZmID0gbWluLnNpemUoKSA+IG1heC5zaXplKCkgPyBtaW4uc2l6ZSgpIC0gbWF4LnNpemUoKQoJCQkJCQkJCQkgICA6IG1heC5zaXplKCkgLSBtaW4uc2l6ZSgpOwoJaWYoZGlmZiA9PSAyKQoJCWJhbGFuY2VfaGVhcHMobWluLCBtYXgpOwp9CgovLyDQktGL0YfQuNGB0LvQtdC90LjQtSDQvNC10LTQuNCw0L3RiyDRgdGA0LXQtNC4INCy0YHQtdGFINGN0LvQtdC80LXQvdGC0L7Qsi4KLy8g0JXRgdC70Lgg0YfQuNGB0LvQviDRjdC70LXQvNC10L3RgtC+0LIg0YfQtdGC0L3QvtC1LCDQvNC10LTQuNCw0L3QsCDQstGL0YfQuNGB0LvRj9C10YLRgdGPINC60LDQuiDRgdGA0LXQtNC90LUg0LDRgNC40YTQvNC10YLQuNGH0LXRgdC60L7QtQovLyDQtNCy0YPRhSDRhtC10L3RgtGA0LDQu9GM0L3Ri9GFINGN0LvQtdC80LXQvdGC0L7QsiDQsiDRg9C/0L7RgNGP0LTQvtGH0LXQvdC90L7QuSDQv9C+0YHQu9C10LTQvtCy0LDRgtC10LvRjNC90L7RgdGC0LgKZG91YmxlIGZpbmRfbWVkaWFuKHZlY3RvcjxpbnQ+JiBtaW4sIHZlY3RvcjxpbnQ+JiBtYXgpCnsKCWlmKG1pbi5zaXplKCkgPT0gbWF4LnNpemUoKSkKCXsKCQlwb3BfaGVhcChtaW4uYmVnaW4oKSwgbWluLmVuZCgpLCBncmVhdGVyPGludD4oKSk7CgkJcG9wX2hlYXAobWF4LmJlZ2luKCksIG1heC5lbmQoKSwgbGVzczxpbnQ+KCkpOwoJCXJldHVybiAobWluLmJhY2soKSArIG1heC5iYWNrKCkpIC8gMi4wOwoJfWVsc2V7CgkJcG9wX2hlYXAobWluLmJlZ2luKCksIG1pbi5lbmQoKSwgZ3JlYXRlcjxpbnQ+KCkpOwoJCXJldHVybiBtaW4uYmFjaygpOwoJfQp9CgppbnQgbWFpbigpCnsKCXN0ZDo6dmVjdG9yPGludD4gbWluX2hlYXA7CglzdGQ6OnZlY3RvcjxpbnQ+IG1heF9oZWFwOwoKCWludCB2YWx1ZTsKCXdoaWxlKHN0ZDo6Y2luID4+IHZhbHVlKQoJewoJCXB1c2hfbmV3X3ZhbHVlKG1pbl9oZWFwLCBtYXhfaGVhcCwgdmFsdWUpOwoJCXN0ZDo6Y291dCA8PCBzdGQ6OnNldHByZWNpc2lvbigyKSA8PCBmaW5kX21lZGlhbihtaW5faGVhcCwgbWF4X2hlYXApIDw8IHN0ZDo6ZW5kbDsKCX0KfQ==