924C - Riverside Curio - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

// Shorthands
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define endl "\n"

#define int long long
#define ll long long
#define ld long double
#define vll vector<ll>
#define vvll vector<vll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll, ll>
#define vpll vector<pll>
#define ff first
#define ss second
#define fill(a, b) memset(a, b, sizeof(a))
#define tll tuple<ll, ll, ll>
#define vtll vector<tll>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define vect(a, n) \
    vll a(n);      \
    rep(i, 0, n) cin >> arr[i];
#define all(a) a.begin(), a.end()
#define sortall(a) sort(a.begin(), a.end());
#define PI acos(-1)
#define print cout <<

void solve()
{
    int a;cin>>a;int arr[a];
    rep(i,0,a)cin>>arr[i];
    int mx=0;rep(i,0,a)mx=max(mx,arr[i]);
    multiset<int> s;for(auto x: arr)s.insert(x);
    int cost=0;
    for(int i=a-1;i>=0;i--){
        if(mx>*(--s.end())){
            mx--;
        }
        cost+=mx-arr[i];
        auto it=s.lower_bound(arr[i]);s.erase(it);
    }
    cout<<cost<<endl;
}
signed main()
{
    fastio int t;
    t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }
}