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
#include <cstdio>
#include <list>
#include <map>
#include <queue>
#define MAXN 200004
#define INF 1000000000000000000ll
#define lld long long int

using namespace std;


int n, m;
lld t[MAXN];
int d[MAXN];

struct event {
	int num;
	lld count;
	lld start;
	lld cDelay;
	event(int num, lld count, lld start, lld cDelay) {
		this->num = num;
		this->count = count;
		this->start = start;
		this->cDelay = cDelay;
	}
};

list <event> ev;

struct heapEntry {
	int num;
	lld time;
	list<event>::iterator it;
	heapEntry(int num, lld time, list<event>::iterator it) {
		this->num = num;
		this->time = time;
		this->it = it;
	}
};

bool operator < (const heapEntry &m1, const heapEntry &m2) {
	return m1.time > m2.time;
}

priority_queue<heapEntry> pq;

map<int, lld> results;

lld sumDelay;
lld sumNNm1p2;

char exists[MAXN]; // if so the group is still valid

int main() {
	scanf("%d%d", &n, &m);

	ev.push_back(event(0, 1, 0, 0));
	auto pt = ev.begin();
	exists[0] = 1;
	int last = 0;

	for (int i = 1; i <= n; i++) {
		scanf("%lld", &t[i]);
		if (t[i] == t[i - 1]) {
			pt->count++;
		} else {

			lld joinTime = (t[i] - pt->start + pt->count - 1) / pt->count;
			pq.push(heapEntry(last, joinTime, pt));
			sumNNm1p2 += (pt->count) * (pt->count - 1) / 2;
			last = i;
			ev.push_back(event(i, 1, t[i], 0));
			pt++;
			exists[i] = 1;
		}
	}
	pq.push(heapEntry(last, INF, pt));
	sumNNm1p2 += (pt->count) * (pt->count - 1) / 2;

	for (int i = 0; i < m; i++) {
		scanf("%d", &d[i]);
		results[d[i]] = 0ll;
	}

	for (auto &e : results) {
		// printf("%d:\n", e.first);
		while (pq.top().time <= e.first) {
			heapEntry ent = pq.top();
			pq.pop();
			if (!exists[ent.num]) continue;

			//printf("(%lld %lld\n", ent.time, ent.num);
			auto it1 = ent.it, it2 = ent.it;
			it2++;
			if (it2 != ev.end()) {
				exists[it2->num] = 0;
				sumNNm1p2 -=  ((it1->count) * (it1->count - 1) + (it2->count) * (it2->count - 1)) / 2;
				it1->count = it1->count + it2->count;
				sumNNm1p2 += (it1->count) * (it1->count - 1) / 2;
				sumDelay += (it2->start - it1->start) * it2->count;
				it1->cDelay = it1->cDelay + it2->cDelay + (it2->start - it1->start) * it2->count;
				it2++;
				if (it2 != ev.end()) {
					lld joinTime = (it2->start - it1->start + it1->count - 1) / it1->count;
					pq.push(heapEntry(it1->num, joinTime, it1));
				}

				ev.erase(++it1);
			}

		}
		e.second = e.first * sumNNm1p2 - sumDelay;
	}

	for (int i = 0; i < m; i++) {
		printf("%lld\n", results[d[i]]);
	}
	return 0;
}