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
#include <bits/stdc++.h>

#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 VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}


using namespace std;

const int max_n = 200005;

int n, m;
lint ANS[max_n];

lint SUMA = 0;
lint COEF = 0;

lint wsp[max_n];
vector<PII> d;
vector<lint> t;
HEAP <pair<lint, PII> > que;
int nxt[max_n];
int prev[max_n];
set<PII> usuniete;

int main() {
	read2(n, m);
	t.pb(0);
	FOR(i,0,n) {
		lint x; scanf("%lld", &x);
		t.pb(x);
	}
	FOR(j,0,m) {
		make(a);
		d.pb(mp(a, j));
	}
	sort(all(d));
	reverse(all(d));

	FOR(i,0,n+1) wsp[i] = 1;
	FOR(i,0,n) nxt[i] = i+1;
	nxt[n] = -1;
	//USTAW
	FOR(i,0,n) {
		que.push(mp(-(t[i+1]-t[i]),mp(i, i+1)));
	}
	while (!d.empty()) {
		while (!que.empty() && usuniete.find(que.top().nd) != usuniete.end()) {
			que.pop();
			//debug("USUWAM");
		}
		while (que.empty() || (-que.top().st >= d.back().st)) {
			ANS[d.back().nd] = SUMA + COEF * 1LL * d.back().st;
		//	debug2(d.back().nd, ANS[d.back().nd]);
			d.pop_back();
			if (d.empty()) break;
		}
		if (que.empty() || d.empty()) continue;
		// WYBIERZ NAJMNIEJSZA DZIURE I MERDZUJ
		//cerr << " DZIURA " << endl;
		int lewo = que.top().nd.st;
		int prawo = que.top().nd.nd;
		//debug2(lewo, prawo);
		int poprawo = nxt[prawo];
		que.pop();
		if (poprawo != -1) usuniete.insert(mp(prawo, poprawo));
		nxt[lewo] = poprawo;
		if (poprawo != -1) {
			que.push(mp(-(t[poprawo]-t[lewo])/(poprawo-lewo), mp(lewo, poprawo)));
			//debug3("PUSHUJE", lewo, poprawo);
		}
		SUMA += wsp[prawo] * 1LL * (t[lewo]-t[prawo]);
		COEF += - (wsp[lewo] * 1LL * (wsp[lewo] + 1))/2 - (wsp[prawo] * 1LL * (wsp[prawo]+1))/2 + ((wsp[lewo]+wsp[prawo])*(wsp[lewo]+wsp[prawo]+1))/2;
		wsp[lewo] += wsp[prawo];
		//debug2(que.size(), d.size());
	}
	FOR(i,0,m) {
		printf("%lld\n", ANS[i]);
	}
}