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
119
120
121
122
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

typedef long long ll;

const int nax = 1e6 + 5;

int g[nax];
vector<int> inv[nax];
ll sum[nax], leftmost[nax];

ll would[nax];

vector<pair<int,int>> events[nax];

void addEvent(int a, int b, ll when) {
	assert(when >= 0);
	if(when < nax)
		events[when].push_back({a, b});
}

ll sufit(ll a, ll b) {
	return (a + b - 1) / b;
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	vector<ll> in(n+1, 0LL);
	++n;
	
	set<int> starts;
	
	for(int i = 0; i < n; ++i) {
		if(i) scanf("%lld", &in[i]);
		leftmost[i] = in[i];
		g[i] = i;
		inv[i] = {i};
		if(i) addEvent(i - 1, i, in[i] - in[i-1]);
		starts.insert(i);
	}
	
	ll A = 0, B = 0;
	
	auto pairs = [&] (ll x) {
		return x * (x - 1) / 2;
	};
	auto add = [&] (int x, int mul) {
		assert(g[x] == x);
		A += mul * pairs(inv[x].size());
		B += mul * (leftmost[x] * inv[x].size() - sum[x]);
	};
	
	for(int single = 0; single < nax; ++single) {
		for(int i = 0; i < (int) events[single].size(); ++i) {
			pair<int,int> p = events[single][i];
			int a = g[p.first], b = g[p.second];
			if(a == b) continue;
			debug() << "start";
			//~ debug() << imie(a) imie(b) imie(starts);
			add(a, -1);
			add(b, -1);
			if(inv[a].size() > inv[b].size()) swap(a, b);
			for(int x : inv[a]) {
				inv[b].push_back(x);
				g[x] = b;
			}
			inv[a].clear();
			leftmost[b] = min(leftmost[b], leftmost[a]);
			sum[b] += sum[a];
			add(b, 1);
			starts.erase(a);
			debug() << "a";
			auto it = starts.find(b);
			assert(it != starts.end());
			if(it != starts.begin()) {
				auto it2 = prev(it);
				addEvent(*it2, *it, sufit(leftmost[*it] - leftmost[*it2], inv[*it2].size()));
			}
			auto it2 = next(it);
			if(it2 != starts.end())
				addEvent(*it, *it2, sufit(leftmost[*it2] - leftmost[*it], inv[*it].size()));
			debug() << "b";
		}
		//~ debug() << imie(A) imie(B);
		would[single] = A * single + B;
	}
	
	while(q--) {
		int single;
		scanf("%d", &single);
		printf("%lld\n", would[single]);
	}
}