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
#include <cstdio>
#include <vector>
#include <algorithm>

struct Crop {
	Crop(int p, long long int d, long long int h): 
		pos(p), 
		day(d), 
		height(h) 
	{
	}

	bool operator<(const Crop &rhs) const {
		return pos < rhs.pos;
	}
	
	int pos;
	long long int day;
	long long int height;
};

int N,M;
int inc[500100];
long long int sum[500100];
std::vector<Crop> crops;

long long int getHeight(int pos, long long int day) {
	int x = std::upper_bound(crops.begin(), crops.end(), Crop(pos,0,0)) - crops.begin() - 1;
	return (day - crops[x].day) * inc[pos] + crops[x].height;
}

int findFirst(long long int day, long long int height) {
	int left=1,right=N+1;

	while (left < right) {
		int mid = (left + right) / 2;
		if (getHeight(mid,day) < height) left = mid+1;
		else right = mid;
	}
	
	return left;
}

int main() {
	scanf("%d %d",&N,&M);
	for (int i=1; i<=N; ++i) {
		scanf("%d",&inc[i]);
	}

	sum[0] = 0;
	std::sort(inc+1,inc+N+1);
	for (int i=1; i<=N; ++i) {
		sum[i] = inc[i] + sum[i-1];
	}

	crops.push_back(Crop(0,0,0));

	for (int i=0; i<M; ++i) {
		int first;
		int last = N;
		long long int day,height;
		long long int res = 0;

		scanf("%lld %lld",&day,&height);
		first = findFirst(day, height);

		while (crops.rbegin()->pos >= first) {
			Crop crop = *crops.rbegin();
			crops.pop_back();
			res += (day - crop.day)	* (sum[last] - sum[crop.pos-1]) + (crop.height - height) * (last - crop.pos + 1);
			last = crop.pos-1;
		}

		res += (day - crops.rbegin()->day) * (sum[last] - sum[first-1]) + (crops.rbegin()->height - height) * (last - first + 1);
		crops.push_back(Crop(first,day,height));
		printf("%lld\n",res);
	}

	return 0;
}