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
#include <bits/stdc++.h>
#define int long long
#define pi pair<int, int>

using namespace std;

int solve(vector<int> &A, int k, int l, int r){
  if(l>=r) return 0;
  pi biggest = {-1, -1};
  for(int i=l; i<=r; i++)
    biggest=max(biggest, {A[i], i});

  int res=0;
  int ind = biggest.second;
  if(ind > l){
    if(A[ind]-A[ind-1] > k){
      res += (A[ind]-k)-(A[ind-1]);
      A[ind-1] = A[ind]-k;
    }
  }
  if(ind < r){
    if(A[ind]-A[ind+1] > k){
      res += (A[ind]-k)-(A[ind+1]);
      A[ind+1] = A[ind]-k;
    }
  }

  return (int)(res + solve(A, k, l, ind-1) + solve(A,k, ind+1, r));
};

signed main(){
  int n, k; cin >> n >> k;
  vector<int> A(n);
  for(auto &a : A) cin >> a;

     auto fact = [&](this auto fact, int x) -> int {
        return x ? x * fact(x - 1) : 1;
    };

  cout << solve(A, k,0, n-1)<<'\n';
}