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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#ifdef LOCAL
template <class T, class U>
ostream& operator<<(ostream& os, pair<T, U> p) {
	return os << "(" << p.first << ", " << p.second << ")";
}

template<template<class, class...> class C, class... A>
typename enable_if<!is_same<C<A...>, string>::value, ostream&>::type
operator<<(ostream& os, C<A...> c) {
	auto i = c.begin();
	while (i != c.end()) {
		os << " {"[i == c.begin()] << *i;
		os << ",}"[++i == c.end()];
	}
	return os;
}

#define debug(x) { cerr << #x << " = " << x << endl; }
#else
#define debug(...) {}
#endif


template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 200 * 1000 + 5;

int size[N];
long long begining[N];
long long ending[N];
int last_event[N];
ordered_set<pair<long long, int>> clients;

#ifdef LOCAL
const int T = 10;
#else
const int T = 1000 * 1000 + 6;
#endif

vector<int> zda[T];

long long ans[T];

long long wzo(int x) {
	return ((long long)x * (x-1)) / 2;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	clients.insert({0, 0});
	size[0] = 1;
	for (int i = 1; i <= n; i ++) {
		long long a;
		scanf("%lld", &a);
		size[i] = 1;
		begining[i] = a;
		ending[i] = a;
		clients.insert({a, i});
	}
	pair<long long,int> last = {-1, -1};
	for (auto now : clients) {
		if (last.second != -1) {
			if (now.first - last.first < T) zda[now.first - last.first].push_back(last.second);
		}
		last = now;
	}
	long long wynik = 0;
	long long delta = 0;
	for (int t = 0; t < T; t ++) {
		for (int i = 0; i < zda[t].size(); i ++) {
			auto x = zda[t][i];
			ending[x] += (long long)size[x] * (t - last_event[x]);
			last_event[x] = t;
			if (size[x] == 0) continue;
			debug(x);
			int k = clients.order_of_key({begining[x], x});
			auto nast = *clients.find_by_order(k + 1);
			assert(begining[nast.second] <= ending[x]);
			wynik += (ending[x] - begining[nast.second]) * (long long)size[nast.second];
			clients.erase(nast);
			int y = nast.second;
			ending[y] += (long long)size[y] * (t - last_event[y]);
			ending[y] += ending[x] - begining[y];
			ending[x] = ending[y];
			delta -= wzo(size[x]);
			delta -= wzo(size[y]);
			size[x] += size[y];
			delta += wzo(size[x]);
			size[y] = 0;
			if ((int)clients.size() > k + 1) {
				nast = *clients.find_by_order(k + 1);
				if (t + (nast.first - ending[x] + size[x] - 1) / size[x] < T)
					zda[t + (nast.first - ending[x] + size[x] - 1) / size[x]].push_back(x);
			}
		}
		ans[t] = wynik;
		debug(t);
		debug(wynik);
		debug(clients.size());
		wynik += delta;
	}
	for (int i = 0; i < m; i ++) {
		int t;
		scanf("%d", &t);
		printf("%lld\n", ans[t]);
	}
}