1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define mkp make_pair
#define fir first
#define sec second
#define pb push_back
using namespace std;
const int MaxN = 500010;
priority_queue <int, vector <int>, greater<int> > small[MaxN];
priority_queue <int, vector <int>, less<int> > large[MaxN];
int stot;
int n, a[MaxN];
int iabs(int x) { return x < 0 ? -x : x; }
int calc(int now) {
    return small[now].top();
}
void insert(int s, int x) {
    if (x < small[s].top()) large[s].push(x);
    else small[s].push(x);
    if (large[s].size() > small[s].size()) {
        small[s].push(large[s].top());
        large[s].pop();
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX