3666.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void insertSort(vector<int> &l, int n) {
    int low = lower_bound(l.begin(), l.end(), n) - l.begin();
    //cout << low << endl;
    l.insert(l.begin() + low, n);
}

vector<int> min_medians;
vector<int> min_medians_pos;

void get_min_medians(vector<int> l) {
    vector<int> min_l;
    int current_pos = 0;
    for (int i = 0; i < l.size(); i++) {
        if (min_l.size() == 0) {
            min_l.push_back(l[i]);
            min_medians.push_back(l[i]);
            min_medians_pos.push_back(i);
            continue;
        }
        
        int m = min_l[(min_l.size()-1)/2];
        if (l[i] < m) {
            min_l.clear();
            min_l.push_back(l[i]);
            min_medians.push_back(l[i]);
            min_medians_pos.push_back(i);
        } else {
            insertSort(min_l, l[i]);
            int m = min_l[(min_l.size()-1)/2];
            for (int j = i - min_l.size(); j >= 0; j--) {
                if (min_medians[j] < m) {
                    insertSort(min_l, l[j]);
                    m = min_l[(min_l.size()-1)/2];
                } else {
                    break;
                }
            }
            
            min_medians.push_back(min_l[(min_l.size()-1)/2]);
            min_medians_pos.push_back(i - min_l.size() + 1);
        }
    }
}

int f(vector<int> l, int low, int high, int minimum=1) {
    if (high - low == 0) return 0;
    if (high - low == 1) {
        return abs(l[low] - max(l[low], minimum));
    }
    
    int medians_min = min_medians[high-1];
    int index = min_medians_pos[high-1];
    //cout << index << " " << medians_min << endl;
    int m = max(minimum, medians_min);
    
    int sum = 0;
    for (int i = index; i < high; i++) {
        sum += abs(m - l[i]);
    }
    return f(l, 0, index, m) + sum;
}

int main()
{
        int n;
        cin >> n;
        vector<int> l;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            l.push_back(x+1);
        }
        //int a = f(l, 0, n);
        reverse(l.begin(), l.end());
        get_min_medians(l);
        //for (int i = 0; i < min_medians.size(); i++) {
        //    cout << i << " " << min_medians[i] << " " << min_medians_pos[i] << endl;
        //}
        int b = f(l, 0, n);
        cout << b << endl;
        //cout << min(a, b) << endl;
}