#include <iostream>
#include <iomanip>
#include <queue>
#include <vector>
#include <algorithm>
using std::vector;
using std::greater;
using std::less;
class RunningMedian
{
private:
std::priority_queue<int> max_heap;
std::priority_queue<int, vector<int>, greater<int>> min_heap;
public:
void push(int value)
{
// adding the number into the proper heap
if(max_heap.empty())
max_heap.push(value);
else{
if(value >= max_heap.top())
max_heap.push(value);
else
min_heap.push(value);
}
// balancing heaps
if (max_heap.size() - min_heap.size() == 2)
{
min_heap.push(max_heap.top());
max_heap.pop();
}
else if (min_heap.size() - max_heap.size() == 2)
{
max_heap.push(min_heap.top());
min_heap.pop();
}
}
double median()
{
if (max_heap.size() == min_heap.size())
return (max_heap.top() + min_heap.top()) / 2.0;
else if (max_heap.size() > min_heap.size())
return max_heap.top();
else
return min_heap.top();
}
};
int main(){
RunningMedian solver;
int n, value;
std::cin >> n;
for(int i = 0; i < n; i++)
{
std::cin >> value;
solver.push(value);
std::cout << std::fixed << std::setprecision(2) << solver.median() << std::endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgc3RkOjp2ZWN0b3I7CnVzaW5nIHN0ZDo6Z3JlYXRlcjsKdXNpbmcgc3RkOjpsZXNzOwoKY2xhc3MgUnVubmluZ01lZGlhbgp7CnByaXZhdGU6CiAgICBzdGQ6OnByaW9yaXR5X3F1ZXVlPGludD4gbWF4X2hlYXA7CiAgICBzdGQ6OnByaW9yaXR5X3F1ZXVlPGludCwgdmVjdG9yPGludD4sIGdyZWF0ZXI8aW50Pj4gbWluX2hlYXA7CiAgICAKcHVibGljOgogICAgdm9pZCBwdXNoKGludCB2YWx1ZSkKICAgIHsKICAgICAgICAvLyBhZGRpbmcgdGhlIG51bWJlciBpbnRvIHRoZSBwcm9wZXIgaGVhcAogICAgICAgIGlmKG1heF9oZWFwLmVtcHR5KCkpCgkgICAgICAgbWF4X2hlYXAucHVzaCh2YWx1ZSk7CiAgICAgICAgZWxzZXsKCSAgICAgICBpZih2YWx1ZSA+PSBtYXhfaGVhcC50b3AoKSkKCSAgICAgICAgICAgbWF4X2hlYXAucHVzaCh2YWx1ZSk7CgkgICAgICAgZWxzZQoJICAgICAgICAgICBtaW5faGVhcC5wdXNoKHZhbHVlKTsKICAgICAgICB9CiAgICAgICAgLy8gYmFsYW5jaW5nIGhlYXBzCiAgICAgICAgaWYgKG1heF9oZWFwLnNpemUoKSAtIG1pbl9oZWFwLnNpemUoKSA9PSAyKQogICAgICAgIHsKICAgICAgICAgICAgbWluX2hlYXAucHVzaChtYXhfaGVhcC50b3AoKSk7CiAgICAgICAgICAgIG1heF9oZWFwLnBvcCgpOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmIChtaW5faGVhcC5zaXplKCkgLSBtYXhfaGVhcC5zaXplKCkgPT0gMikKICAgICAgICB7CiAgICAgICAgICAgIG1heF9oZWFwLnB1c2gobWluX2hlYXAudG9wKCkpOwogICAgICAgICAgICBtaW5faGVhcC5wb3AoKTsKICAgICAgICB9CiAgICB9CiAgICAKICAgIGRvdWJsZSBtZWRpYW4oKQogICAgewogICAgICAgIGlmIChtYXhfaGVhcC5zaXplKCkgPT0gbWluX2hlYXAuc2l6ZSgpKQogICAgICAgICAgICByZXR1cm4gKG1heF9oZWFwLnRvcCgpICsgbWluX2hlYXAudG9wKCkpIC8gMi4wOwogICAgICAgIGVsc2UgaWYgKG1heF9oZWFwLnNpemUoKSA+IG1pbl9oZWFwLnNpemUoKSkKICAgICAgICAgICAgcmV0dXJuIG1heF9oZWFwLnRvcCgpOwogICAgICAgIGVsc2UKICAgICAgICAgICAgcmV0dXJuIG1pbl9oZWFwLnRvcCgpOwogICAgfQp9OwoKaW50IG1haW4oKXsKICAgIFJ1bm5pbmdNZWRpYW4gc29sdmVyOwoJaW50IG4sIHZhbHVlOwogICAgCiAgICBzdGQ6OmNpbiA+PiBuOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgIHsKICAgICAgICBzdGQ6OmNpbiA+PiB2YWx1ZTsKICAgICAgICBzb2x2ZXIucHVzaCh2YWx1ZSk7CiAgICAgICAgc3RkOjpjb3V0IDw8IHN0ZDo6Zml4ZWQgPDwgc3RkOjpzZXRwcmVjaXNpb24oMikgPDwgc29sdmVyLm1lZGlhbigpIDw8IHN0ZDo6ZW5kbDsKICAgIH0KCXJldHVybiAwOwp9