# CFR 713 C. Sonya and Problem Wihtout a Legend ( Priority Queue + Median + Smaller to Larger )

Problem - 713C - Codeforces

```typedef priority_queue<int> gpq;
typedef priority_queue<int, vi, greater<int> > lpq;

int N;
vi _A;

void init() {
cin >> N;
_A = vi(N);
for (int i = 0; i < N; ++i) cin >> _A[i];
}

vi A;

void preprocess() {
A = vi(N);
for (int i = 0; i < N; ++i) A[i] = _A[i] - i;
}

void merge(tuple<gpq, lpq>& a, tuple<gpq, lpq>& b) {
if (not(get<0>(a).size() + get<1>(a).size() >=
get<0>(b).size() + get<1>(b).size()))
swap(a, b);
while (not get<0>(b).empty()) {
int u = get<0>(b).top();
get<0>(b).pop();
if (u <= get<0>(a).top())
get<0>(a).emplace(u);
else
get<1>(a).emplace(u);
}
while (not get<1>(b).empty()) {
int u = get<1>(b).top();
get<1>(b).pop();
if (u <= get<0>(a).top())
get<0>(a).emplace(u);
else
get<1>(a).emplace(u);
}
while (abs((int)get<0>(a).size() - get<1>(a).size()) > 1) {
if (get<0>(a).size() < get<1>(a).size())
get<0>(a).emplace(get<1>(a).top()), get<1>(a).pop();
else
get<1>(a).emplace(get<0>(a).top()), get<0>(a).pop();
}
}

int get_median(tuple<gpq, lpq>& t) {
gpq& a = get<0>(t);
lpq& b = get<1>(t);
if (a.size() > b.size()) return a.top();
return b.top();
}

void solve() {
vector<tuple<gpq, lpq> > seq;
for (int i = 0; i < N; ++i) {
gpq a;
lpq b;
a.emplace(A[i]);
seq.emplace_back(a, b);
while (seq.size() >= 2 and
get_median(seq[(int)seq.size() - 2]) > get_median(seq.back()))
merge(seq[(int)seq.size() - 2], seq.back()), seq.pop_back();
}
ll ans = 0;
for (int i = 0, ptr = 0; ptr < seq.size(); ++ptr) {
int med = get_median(seq[ptr]);
int sz = get<0>(seq[ptr]).size() + get<1>(seq[ptr]).size();
for (int j = 0; j < sz; ++j) ans += abs(A[i + j] - med);
i += sz;
}
cout << ans << endl;
}
```