1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <vector>

using namespace std;

int main() {

  int n, k; scanf("%d %d", &n, &k);
  vector<int> a(n), b(n, 0);
  for (int i=0; i<n; ++i) scanf("%d", &a[i]);
  b[0] = a[0];
  for (int i=1; i<n; ++i) b[i] = max(a[i], b[i-1] - k);
  for (int i=n-1; i>=0; --i) b[i] = max(b[i], b[i+1]-k);

  long long res = 0;
  for (int i=0; i<n; ++i) res += b[i] - a[i];
  printf("%lld\n", res);

  return 0; 
}