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
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <queue>
#define mp make_pair
using namespace std;

long long czas[300001];
int ojc[300001];
int roz[300001];
int mn[300001];
int find(int poz)
{
	if(ojc[poz]==-1) return poz;
	ojc[poz]=find(ojc[poz]);
	return ojc[poz];
}
void merge(int a, int b)
{
	int fa=find(a);
	int fb=find(b);
	if(fa!=fb)
	{
		if(roz[fa]<roz[fb])
		{
			fa^=fb;
			fb^=fa;
			fa^=fb;
		}
		roz[fa]+=roz[fb];
		ojc[fb]=fa;
		mn[fa]=min(mn[fa], mn[fb]);
	}
}

long long pre[2000001];
long long dod[2000001];

int main()
{
	long long n, m;
	scanf("%lld%lld", &n, &m);
	for(int i=0; i<=n; i++) ojc[i]=-1;
	for(int i=0; i<=n; i++) roz[i]=1;
	for(int i=0; i<=n; i++) mn[i]=i;
	for(int i=1; i<=n; i++) scanf("%lld", &czas[i]);
	czas[n+1]=1e18;
	priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater<pair <long long, int> > > kol;
	for(int i=1; i<=n; i++) 
	{
		kol.push(mp(czas[i]-czas[i-1], i-1));
	}
	while(!kol.empty())
	{
		pair <long long, int> akt=kol.top();
		kol.pop();
		if(akt.first>1000000) break;
		int f1=find(akt.second);
		int f2=find(akt.second+1);
		if(f1!=f2)
		{
			long long r1=roz[f1], r2=roz[f2];
			pre[akt.first+1]-=r1*(r1-1)/2;
			pre[akt.first+1]-=r2*(r2-1)/2;
			merge(f1, f2);
			int nf=find(f1);
			long long nr=roz[nf];
			int pier=mn[nf];
			assert(nr==r1+r2);
			pre[akt.first+1]+=nr*(nr-1)/2;
			dod[akt.first]+=(akt.first*r1-(czas[akt.second+1]-czas[pier]))*r2;
			kol.emplace((long long)ceil((double)(czas[pier+nr]-czas[pier])/(nr)), pier+nr-1);
		}
	}
	for(int i=1; i<=1000000; i++) pre[i]+=pre[i-1];
	for(int i=1; i<=1000000; i++) pre[i]+=pre[i-1]+dod[i];
	for(int i=0, a; i<m; i++)
	{
		scanf("%d", &a);
		printf("%lld\n", pre[a]);
	}
}