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
123
124
125
126
127
128
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
#include <tuple>

using namespace std;

struct pointInTime {
	long long int time;
	int guest_count;
	int prev_point;
	inline bool operator <(const pointInTime &p2) const {
		return time < p2.time;
	}
};

struct oven {
	int bTime;
	int id;
	inline bool operator <(const oven &p2) const {
		return bTime < p2.bTime;
	}
};

struct Event {
	int minZ;
	int idd;
	bool start;
public:
	bool operator< (const Event &p2) const {
		return minZ > p2.minZ;
	}
};

typedef priority_queue<Event> qType ;

void initialize(vector<pointInTime> t, qType &q) {
	for (int i = 1; i < (int)t.size(); ++i) {
		q.push({ (int)(t[i].time - t[i-1].time) / t[i-1].guest_count + (((t[i].time - t[i - 1].time) % (t[i - 1].guest_count)) ? 1:0), i, true });
	}
}

void querry(qType &q, long long &curT, long long &AllT, long long int nextT, int &partial, vector<pointInTime> t) {
	Event e = q.top();
	q.pop();
	AllT += partial * (e.minZ - curT);
	curT = e.minZ;
	if (e.start) {
		if (t[e.idd].prev_point == -1) return;
		pointInTime& poprzedni = t[t[e.idd].prev_point];
		if (e.idd + 1 < (int)t.size()) t[e.idd + 1].prev_point = t[t[e.idd].prev_point].prev_point;
		AllT += (poprzedni.guest_count * nextT + poprzedni.time) - t[e.idd].time ;
		if(poprzedni.guest_count > 1)
		q.push({ (int)
			(t[e.idd].time - poprzedni.time) / (poprzedni.guest_count-1) + (((t[e.idd].time - poprzedni.time) % (poprzedni.guest_count -1)) ? 1 : 0)
			, e.idd, false });

		poprzedni.guest_count += t[e.idd].guest_count;
		t[e.idd].prev_point = -1;
		++partial;
	}
	else {
		--partial;
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	long long int * t_in = new long long int[n];
	vector<pointInTime> t;
	

	long long int constant_factor = 0;
	long long int firstT;
	cin >> firstT;
	t_in[0] = 0;
	for (int i = 1; i < n; ++i) {
		cin >> t_in[i];
		t_in[i] -= firstT;
	}
	
	t.push_back({0, 1, -1 });
	for (int i = 1; i < n; ++i) {
		if (t_in[i] == t.back().time) t.back().guest_count++;
		else {
			constant_factor += (t.back().guest_count - 1) * t.back().guest_count / 2;
			t.push_back({ t_in[i], 1, (int)t.size() - 1 });
		}
	}

	constant_factor += (t.back().guest_count - 1) * t.back().guest_count / 2;
	delete[] t_in;

	oven* p = new oven[m];
	for (int i = 0; i < m; ++i) {
		cin >> p[i].bTime;
		p[i].id = i;
	}
	sort(p, p + m);
	qType q;
	initialize(t, q);

	int partial = 0;
	long long int AllT = 0, curT = 0;

	long long int * res = new long long int[m];
	for (int i = 0; i < m; ++i) {
		
		int nextT = p[i].bTime;
		while (!q.empty() && q.top().minZ <= nextT) {
			querry(q, curT, AllT, nextT, partial, t);
		}
		AllT += partial * (nextT - curT);
		curT = nextT;
		res[p[i].id] = AllT + max(0ll, nextT - firstT);
	}
	for (int i = 0; i < m; ++i) {
		cout << res[i] - 1 << "\n";
	}
}