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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define F first
#define S second
#if true
#define int long long
#undef INT_MAX
#define INT_MAX LLONG_MAX
#endif
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
template <class T> using MinTree = priority_queue<T, vector<T>, greater<T>>;
template <class T> using MaxTree = priority_queue<T>;

// start of extra functions
#define all(v) (v).begin(), (v).end()
#define loop(i, n) sloop(0, i, n)
#define sloop(s, i, n) for (int i = (s); i < (n); i++)
#define rloop(i, n) rsloop(0, i, n)
#define rsloop(s, i, n) for (int i = (n); i-- > (s);)
int binsearch(int l, int h, function<int(int)> o, int m = -69) {
	for (int m; l + 1 < h; (o(m = (l + h) / 2) ? h : l) = m)
		;
	return l + 1;
}
int powint(int a, int b, int m = INT_MAX, int o = 1) {
	return a %= m, b ? powint(a * a, b / 2, m, (b & 1 ? a : 1) * o) : o;
}
// end of extra functions

// start of extra IO
template <class T, class U> istream &operator>>(istream &s, pair<T, U> &p) {
	return s >> p.F >> p.S;
}
template <class T> istream &operator>>(istream &s, vector<T> &v) {
	loop(i, v.size()) s >> v[i];
	return s;
}
template <class T, class U> ostream &operator<<(ostream &s, pair<T, U> p) {
	return s << '(' << p.F << ", " << p.S << ')';
}
template <class T> ostream &operator<<(ostream &s, vector<T> v) {
	s << '[';
	loop(i, v.size()) s << (i ? ", " : "") << v[i];
	return s << ']';
}
// end of extra IO

// start of dbg definiton
void _dbg(int line, char *fmt) { cout << "[" << line << "]" << fmt << endl; }
template <class T, class... U> void _dbg(int line, char *f, T a, U... r) {
	cout << (*f == ','		      ? f++,
		 string(5 + log10(line), ' ') : "[" + to_string(line) + "]: ");
	while (isspace(*f))
		f++;
	for (int d = 0; *f && (*f != ',' || d > 0);
	     d += strchr("[{(", *f) - strchr("]})", *f))
		cout << *f++;
	cout << " = " << a << endl;
	if (*f)
		_dbg(line, f, r...);
}
#define DBG(...) _dbg(__LINE__, #__VA_ARGS__ __VA_OPT__(, ) __VA_ARGS__);
// end of dbg definition

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	vi v(n);
	cin >> v;
	vi o(n);
	o = v;
	sloop(1, i, n) o[i] = max(o[i], o[i - 1] - k);
	rloop(i, n-1) o[i] = max(o[i], o[i + 1] - k);
	int an = 0;
	loop(i,n) an += o[i] - v[i];
	cout << an;
}