#include "nile.h"
#include <cstring>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vl;
const int N = 100000, N_ = 1 << 17, M = N - 1 + N - 2, Q = 100000; /* N_ = pow2(ceil(log2(N))) */
const long long INF = 0x3f3f3f3f3f3f3f3f;
long long min(long long a, long long b) { return a < b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], aa[N], bb[N], ii[N];
int dd[Q], gg[Q];
int cc[M], hh[M];
int *ww;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (ww[ii[j]] == ww[i_])
j++;
else if (ww[ii[j]] < ww[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
long long dp[N + 1];
long long st[N_ * 2][3][3]; int n_;
void pul(int i) {
int l = i << 1, r = l | 1;
memset(st[i], 0x3f, sizeof st[i]);
for (int a = 0; a < 3; a++)
for (int b = 0; b < 3; b++)
for (int c = 0; c < 3; c++)
st[i][a][c] = min(st[i][a][c], st[l][a][b] + st[r][b][c]);
}
void build(int n) {
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (int i = 0; i < n_; i++) {
memset(st[n_ + i], 0x3f, sizeof st[n_ + i]);
if (i < n)
st[n_ + i][0][0] = aa[i], st[n_ + i][2][1] = aa[i], st[n_ + i][1][0] = bb[i];
else
st[n_ + i][0][0] = 0, st[n_ + i][1][1] = 0;
}
for (int i = n_ - 1; i > 0; i--)
pul(i);
}
void update(int i, int b, int w) {
i += n_;
st[i][0][b] = w;
while (i > 1)
pul(i >>= 1);
}
vl calculate_costs(vi xx_, vi aa_, vi bb_, vi dd_) {
int n = xx_.size(), q = dd_.size();
for (int i = 0; i < n; i++)
xx[i] = xx_[i], aa[i] = aa_[i], bb[i] = bb_[i];
if (n == 1) {
vl ans(q, 0);
for (int h = 0; h < q; h++)
ans[h] = aa[0];
return ans;
}
for (int g = 0; g < q; g++)
dd[g] = dd_[g];
for (int i = 0; i < n; i++)
ii[i] = i;
ww = xx, sort(ii, 0, n);
for (int i = 0; i < n; i++)
xx_[i] = xx[ii[i]], aa_[i] = aa[ii[i]], bb_[i] = bb[ii[i]];
for (int i = 0; i < n; i++)
xx[i] = xx_[i], aa[i] = aa_[i], bb[i] = bb_[i];
int m = n - 1 + n - 2;
for (int i = 0; i + 1 < n; i++)
cc[i] = xx[i + 1] - xx[i];
for (int i = 0; i + 2 < n; i++)
cc[n - 1 + i] = xx[i + 2] - xx[i];
for (int h = 0; h < m; h++)
hh[h] = h;
ww = cc, sort(hh, 0, m);
for (int g = 0; g < q; g++)
gg[g] = g;
ww = dd, sort(gg, 0, q);
build(n);
vl ans(q, 0);
for (int g = 0, h = 0; g < q; g++) {
int g_ = gg[g], d = dd[g_], h_;
while (h < m && cc[h_ = hh[h]] <= d) {
if (h_ + 1 < n)
update(h_, 1, bb[h_]);
else
update(h_ - (n - 1), 2, bb[h_ - (n - 1)]);
h++;
}
ans[g_] = st[1][0][0];
}
return ans;
}
