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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> T;

void solve() {
    int n, k; cin >> n >> k;
    vector<int>a(n+1);
    for (int i = 1; i<=n; i++) cin >> a[i];
    auto b = a;
    set<T>s;
    for (int i = 1; i <= n; i++) s.insert({a[i], i});
    auto process = [&](int idx, int val) {
        bool f = 0;
        auto it = s.lower_bound({a[idx], idx});
        if (it != s.end() && it->second == idx) {
            f = 1;
            s.erase(it);
        }
        b[idx] = max(b[idx], val);
        if (f) s.insert({b[idx], idx});
    };
    while ((int)s.size()){
        auto [val, idx] = *(--(s.end()));
        s.erase(--s.end());
        if (idx >= 2) process(idx - 1, val - k);
        if (idx + 1 <= n) process(idx + 1, val - k);
    }
    // for (int i = 1;i <= n; i++) cout << b[i] << " ";
    // cout << "\n";
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += b[i] - a[i];
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}