#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
multiset<int> local_minimum(multiset<int> s, int h) {
assert((int) s.size() % 2 == 0);
multiset<int> s2;
int slope = -(int) s.size() / 2;
for (auto &x : s) {
if (slope < 0) {
s2.insert(x - h);
}
if (slope >= 0) {
s2.insert(x + h);
}
slope++;
}
return s2;
}
/**
void print(multiset<int> s) {
cout << " : ";
for (auto &x : s) {
cout << x << " ";
}
cout << "\n";
// cout << ", ";
}**/
vector<pair<int, int>> get(multiset<int> s, int a, int b) {
vector<int> xs;
for (auto &it : s) {
xs.push_back(it);
}
int n = (int) xs.size();
vector<pair<int, int>> ret;
ret.push_back({a, b});
for (int i = n - 1; i >= 0; i--) {
/// (a - 1) * x + b2 = a * x + b
/// a * x - x + b2 = a * x + b
/// b2 - x = b
/// b2 = x + b
b += xs[i];
a--;
ret.push_back({a, b});
}
reverse(ret.begin(), ret.end());
return ret;
}
const int c = 100;
void print(multiset<int> s, int b) {
for (auto &x : s) {
cout << x << " ";
}
cout << " :\n";
int a = (int) s.size() / 2;
/**
bug:
3 1
7 7 7
s.clear();
s.insert(2);
s.insert(8);
s.insert(8);
s.insert(8);
b = -24;
a = 4;**/
vector<pair<int, int>> v = get(s, a, b);
int last = -c;
auto ko = s.begin();
s.insert(+c);
for (auto &it : v) {
cout << "for x = " << last << "..." << *ko << " : ";
last = *ko;
ko++;
cout << "f(x) = x * " << it.first << " + " << it.second << "\n";
}
cout << "\n";
}
int solve(multiset<int> s, int b) {
int a = (int) s.size() / 2;
vector<pair<int, int>> v = get(s, a, b);
for (auto &it : v) {
if (it.first == 0) {
return it.second;
}
}
assert(0);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
//freopen ("input", "r", stdin);
multiset<int> s;
int n, h, x, b = 0;
cin >> n >> h >> x;
s.insert(x);
s.insert(x);
b = -x;
for (int i = 2; i <= n; i++) {
s = local_minimum(s, h);
cin >> x;
b -= (i - 1) * h; /// I have no clue why this happens lol
/**if (i == n) {
cout << "lol\n";
print(s, b);
return 0;
}**/
s.insert(x);
s.insert(x);
auto it = s.end();
it--;
b -= x;
// print(s, b);
// cout << "\n";
// return 0;
// cout << " => " << b << "\n";
// print(s, b);
// return 0;
}
int a = (int) s.size() / 2;
/**
bug:
3 1
7 7 7
s.clear();
s.insert(2);
s.insert(8);
s.insert(8);
s.insert(8);
b = -24;
a = 4;**/
vector<pair<int, int>> v = get(s, a, b);
for (auto &it : v)
{
if (it.first == 0) {
cout << it.second << "\n";
}
} // print(s, b);
}
