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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
#define FOR(i,s,e) for(int i=(s);i<=(e);i++)
#define FORD(i,s,e) for(int i=(s);i>=(e);i--)
#define ALL(k) (k).begin(),(k).end()
#define e1 first
#define e2 second
#define mp make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const bool print = false;
const int MAXN = 200111;


LL answer[MAXN];
LL moment[MAXN];

int fu[MAXN];
pair<LL,LL> interv[MAXN];

LL uniontime[MAXN];
LL score = 0;
LL changePerUnit = 0;
LL ovenSize = 0;

int find(int v){
	if(fu[v] < 0) return v;
	fu[v] = find(fu[v]);
	return fu[v];
}
priority_queue<pair<LL,LL> > operations;
int n;
int unia(int a, int b){
	int aa = find(a), bb = find(b);
	if(aa == bb) return 0;
	
	//LL lstart = moment[interv[aa].e1] - ovenSize;
	LL lend = moment[interv[aa].e1] - ovenSize + (-fu[aa]) * ovenSize;
	LL rstart = moment[interv[bb].e1] - ovenSize;
	LL rend = moment[interv[bb].e1] - ovenSize + (-fu[bb]) * ovenSize;
	if(lend < rstart) {
		return 0;
	}
	score += (lend - rstart) * (-fu[bb]);
	int following = find(interv[bb].e2 + 1);
	/*LL time1 = ovenSize + 
	(moment[interv[bb].e2 + 1] - rend - (fu[aa] + fu[bb] + 1)) /
	(-fu[aa]-fu[bb]);*/
	LL time2 =  (moment[interv[bb].e2 + 1] - moment[interv[aa].e1] - (fu[aa] + fu[bb] + 1)) / (-fu[aa] - fu[bb]);
	
	//LL time3 = (moment[interv[following].e2] - moment[interv[aa].e1]) / (-fu[aa] - fu[bb] - fu[following]);
	//if(print)printf("UNIA %d %d %d, %d %d %d\n", aa, bb, following, time1, time2, time3);
	
	uniontime[aa] = uniontime[bb] = time2;
	LL as = -fu[aa], bs = -fu[bb];
	changePerUnit -= (as*(as-1) + bs*(bs-1)) / 2;
	changePerUnit += ((as + bs) * (as + bs - 1)) / 2;
	
	if(fu[aa] > fu[bb]) swap(aa, bb);
	interv[aa].e1 = min(interv[aa].e1, interv[bb].e1);
	interv[aa].e2 = max(interv[aa].e2, interv[bb].e2);
	fu[aa] += fu[bb];
	fu[bb] = aa;
	if(interv[aa].e2 < n)
		operations.emplace(-uniontime[aa], aa);
	return 1;
}



main(){
	int m; scanf("%d%d", &n, &m);
	n++;
	FOR(i, 2, n){
		scanf("%lld", &moment[i]);
	}
	vector<pair<LL,LL> > queries;
	
	
	FOR(i, 1, m){
		LL a;scanf("%lld",&a);
		queries.eb(a,i);
		operations.emplace(-a, -i);
	}
	sort(ALL(queries));
	
	fu[n+1] = -1;
	FOR(i, 1, n){
		fu[i] = -1;
		interv[i] = mp(i, i);
		uniontime[i] = moment[i + 1] - moment[i];
		if(print)printf("%d %lld %lld %lld\n",i,uniontime[i], moment[i+1], moment[i]);
		if(i < n) operations.emplace(-uniontime[i], i);
	}
	while(!operations.empty()){
		LL timeStamp = -operations.top().e1;
		LL element = -operations.top().e2;
		operations.pop();
		score += changePerUnit * (timeStamp - ovenSize);
		if(print)printf("ot %2lld nt %2lld element %2lld score %2lld zmi %2lld\n", ovenSize, timeStamp, element, score, changePerUnit);
		ovenSize = timeStamp;
		if(element < 0){
			element = find(-element);
			//if(fu[element] > 0) continue;
			int nast = interv[element].e2 + 1;
			if(nast > n) continue;
			int ok = unia(element, nast);
			//if(print)printf(" %d \n",ok);
		}
		else{
			answer[element] = score;
		}
	}
	if(print) puts("");
	FOR(i, 1, m) printf("%lld\n",answer[i]);
}