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
84
85
86
87
88
89
90
91
92
93
94
95
//PRZEMYSL ASSERTY
//SPRAWDZ CORNER CASE'Y, MINIMALNE I MAKSYMALNE WEJŚCIE I WYJŚCIE
//MODULO = 1
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <queue>
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define scanf(...) scanf(__VA_ARGS__)?:0
#define e1 first
#define e2 second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
int n,m,ile[200001],fl[200001],fp[200001],tr[1<<19];
ll s1,st,dod,t[200001],ans[200001];
pli roz[200001];
pii d[200001];
int find(int a) {
	if (fl[a]==-1) return a;
	fl[a]=find(fl[a]);
	return fl[a];
}
void Union(int a,int b) {
	int xa=find(a),xb=find(b);
	xa==xb?0:fl[xa]=xb;
}
int find2(int a) {
	if (!fp[a]) return a;
	fp[a]=find2(fp[a]);
	return fp[a];
}
void Union2(int a,int b) {
	int xa=find2(a),xb=find2(b);
	xa==xb?0:fp[xa]=xb;
}
ll licz(int x) {
	return (ll)x*(x+1)/2;
}
void ustaw(int a,pli x) {
	roz[a]=x;
	a=(a+(1<<18))>>1;
	while (a) {
		int nl=tr[a+a],np=tr[a+a+1];
		//printf("%d %d %lld-%d %lld-%d\n",a,tr[a],roz[nl].e1,roz[nl].e2,roz[np].e1,roz[np].e2);
		if (roz[nl]==mp(0ll,0)) {
			tr[a]=np;
			a>>=1;
			continue;
		}
		if (roz[np]==mp(0ll,0)) {
			tr[a]=nl;
			a>>=1;
			continue;
		}
		ll w1=roz[nl].e1*roz[np].e2;
		ll w2=roz[np].e1*roz[nl].e2;
		tr[a]=w1<w2?nl:np;
		a>>=1;
	}
}
int main() {
	scanf("%d%d",&n,&m);
	FOR(i,1,n) scanf("%lld",&t[i]),tr[i+(1<<18)]=i,ustaw(i,mp(t[i]-t[i-1],1)),st+=t[i];
	FOR(i,1,m) scanf("%d",&d[i].e1),d[i].e2=i;
	sort(d+1,d+m+1);
	fill(fl,fl+n+1,-1);
	s1=st;
	int zos=n;
	FOR(i,1,m) {
		while (zos>0 && roz[tr[1]].e1<=(ll)roz[tr[1]].e2*d[i].e1) {
			int nr=tr[1];
			Union(nr,nr-1);
			if (nr>0) Union2(nr-1,nr);
			s1+=(t[find(nr)]-t[nr])*(ile[nr]+1);
			dod-=licz(ile[nr])+licz(ile[find(nr)]);
			ile[find(nr)]+=ile[nr]+1;
			dod+=licz(ile[find(nr)]);
			int pk=find2(nr);
			if (pk!=n) ustaw(pk+1,mp(t[pk+1]-t[find(nr)],pk+1-find(nr)));
			ustaw(nr,mp(0,0));
			zos--;
		}
		ans[d[i].e2]=s1+dod*d[i].e1-st;
	}
	FOR(i,1,m) printf("%lld\n",ans[i]);
}