Найти медианы на всех префиксах последовательности X длины n и вывести их сумму

#pragma comment(linker, "/STACK:167177216")
 
#include <stdio.h>
#include <stack>
#include <math.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string.h>
#include <string>
#include <memory.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <time.h>
#include <cassert>
#include <cstring>
//#include <unordered_set>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef unsigned long long uli;
 
const int INF = 1e9;
const ld eps = 1e-9;
const li MOD = (li)(INF + 7);
const li INF64 = (li)(INF) * (li)(INF);
 
const int ddx[] = {-1, 1, 1, -1};
const int ddy[] = {1, 1, -1, -1};
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dxh[] = {-1, -1, -1, 1, 1, 1, 1, -1};
const int dyh[] = {1, -1, -1, -1, -1, 1, 1, 1};
const string dirs[] = {"RIGHT", "UP", "LEFT", "DOWN"};
 
bool in(int i, int j, int n, int m)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}
 
int a[111111];
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //freopen("errors.txt", "w", stderr);
    //ios_base::sync_with_stdio(false);
    multiset<int> small, big;
    int sz1 = 0, sz2 = 0;
 
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
 
    for(int i = 1; i <= n; i++)
    {
        if(i == 1)
            small.insert(a[i]), sz1++;
        else
        {
            int mx_small = *small.rbegin();
            if(a[i] <= mx_small)
                small.insert(a[i]), sz1++;
            else
                big.insert(a[i]), sz2++;
        }
 
        int cnt = i;
        int SZ1 = (cnt + 1) / 2;
        int SZ2 = cnt - SZ1;
 
        while(sz1 > SZ1)
        {
            multiset<int>::iterator it = small.end();
            it--;
            int val = *it;
            big.insert(val);
            small.erase(it);
            sz1--;
            sz2++;
        }
 
        while(sz1 < SZ1)
        {
            multiset<int>::iterator it = big.begin();
            int val = *it;
            small.insert(val);
            big.erase(it);
            sz1++;
            sz2--;
        }
 
        assert(sz1 - sz2 <= 1);
 
        printf("answer for prefix %d == %d\n", i, *small.rbegin());
    }
    return 0;
}