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
#include <vector>
#include <set>
#include <cstdio>
#include <utility>

typedef std::pair<int, int> PII;

const int M = 201013;
const int Q = 1001013;

long long t[M], sw[M], ret[M];
int nw[M], dd[M];
int n;

long long getA(int i) {
	return ((long long)nw[i]) * (nw[i] + 1) / 2;
}

long long getB(int i) {
	return nw[i] * t[i] - sw[i];
}

void lacz(int i, int j) {
	nw[i] += nw[j] + 1;
	sw[i] += sw[j] + t[j];
	int x = i + nw[i] + 1;
	if (x > n) 
		dd[i] = -1;
	else
		dd[i] = std::min<long long>(Q, (t[x] - t[i] + nw[i]) / (nw[i] + 1));
	if (dd[i] >= Q) dd[i] = -1;
	//printf("%d :: %lld :: %d %lld %d\n", i, t[i], nw[i], sw[i], dd[i]);
}

int main() {
	int m;
	scanf("%d %d",&n,&m);
	std::set<PII> e;
	for (int i = 0; i < n; i++) {
		scanf("%lld", &t[i+1]);
		dd[i] = std::min<long long>(Q, t[i+1] - t[i]);
		if (dd[i] >= Q) 
			dd[i] = -1; 
		else
			e.insert(PII(dd[i], -(i+1)));
	}
	dd[n] = -1;
	for (int i = 0; i < m; i++) {
		int d;
		scanf("%d", &d);
		e.insert(PII(d, i));
	}
	long long A = 0, B = 0;
	while (!e.empty()) {
		int d = e.begin()->first;
		int i = e.begin()->second;
		e.erase(e.begin());
		if (i >= 0) {
			//printf("%lld * %d + %lld\n",A,d,B);
			ret[i] = A*d + B;
		} else {
		  i = -i-1;
			int j = i + 1 + nw[i];
			A -= getA(i);
			B -= getB(i);
			A -= getA(j);
			B -= getB(j);
			if (dd[j] >= 0) e.erase(PII(dd[j], -(j+1)));
			lacz(i, j);
			A += getA(i);
			B += getB(i);
			if (dd[i] >= 0) e.insert(PII(dd[i], -(i+1)));
		}
	}
	for (int i = 0; i < m; i++) printf("%lld\n", ret[i]);
	return 0;
}