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
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

long long n, m;
long long increases[500000];
long long increasesSums[500000];

struct Node {
	long long left;
	long long right;
	long long day;
	long long height;
};

vector<Node> nodes;

long long getSliceWithElement(long long element, long long left, long long right) {
	if (left >= right) {
		return left;
	}

	long long middle = (right + left) / 2;
	if (nodes[middle].left <= element && nodes[middle].right >= element) {
		return middle;
	}else if (nodes[middle].left > element) {
		return getSliceWithElement(element, left, middle-1);
	}
	else {
		return getSliceWithElement(element, middle+1, right);
	}
}

pair<long long, long long> getElementHeightWithSlice(long long element, long long day, long long height) {
	long long slice = getSliceWithElement(element, 0, nodes.size() - 1);

	long long dayDiff = day - nodes[slice].day;
	long long size = dayDiff * increases[element] + nodes[slice].height;

	pair<long long, long long> result;
	result.first = size;
	result.second = slice;

	return result;
}

pair<long long, long long> findFirstCutElement(long long day, long long height, long long left, long long right) {
	pair<long long, long long> result;
	pair<long long, long long> elementWithHeight;
	while (left < right) {
		long long middle = (right + left) / 2;
		elementWithHeight = getElementHeightWithSlice(middle, day, height); //first - size of area, second - slice id

		if (elementWithHeight.first >= height) {
			right = middle - 1;
		}
		else {
			left = middle + 1;
		}
	}
	elementWithHeight = getElementHeightWithSlice(left, day, height);

	result.second = elementWithHeight.second;
	result.first = elementWithHeight.first < height ? left : left-1;
	return result;
}

void calculateCut() {
	long long cutDay, cutHeight;
	scanf("%lld %lld", &cutDay, &cutHeight);

	pair<long long, long long> firstCutElement = findFirstCutElement(cutDay, cutHeight, 0, n - 1); //first - element, second - slice id
	if(firstCutElement.first >= n-1){
		printf("%d\n", 0);
		return;
	}

	firstCutElement.first++;

	long long total = 0;
	long long borderElement = firstCutElement.first;
	long long originalBorderElement = borderElement;
	long long sliceId = firstCutElement.second;
	bool first = true;
	do {
		if (!first) {
			borderElement = nodes[sliceId].left;
		}
		first = false;
		long long dayDiff = cutDay - nodes[sliceId].day;
		total += increasesSums[nodes[sliceId].right] * dayDiff;
		total -= dayDiff * (borderElement > 0 ? increasesSums[borderElement - 1] : 0);
		total -= (cutHeight - nodes[sliceId].height) * (nodes[sliceId].right - borderElement + 1);
	} while (++sliceId < nodes.size());

	printf("%lld\n", total);

	nodes.resize(firstCutElement.second + 1);

	Node nodeToAdd;
	nodeToAdd.left = originalBorderElement;
	nodeToAdd.right = n-1;
	nodeToAdd.day = cutDay;
	nodeToAdd.height = cutHeight;
	nodes[firstCutElement.second].right = originalBorderElement - 1;
	if (nodes[firstCutElement.second].right < nodes[firstCutElement.second].left) {
		nodes.pop_back();
	}
	nodes.push_back(nodeToAdd);

}

int main() {
	scanf("%lld %lld", &n, &m);
	for (long long i = 0; i < n; ++i) {
		scanf("%lld", &(increases[i]));
	}

	sort(increases, increases + n);
	increasesSums[0] = increases[0];
	for (long long i = 1; i < n; ++i) {
		increasesSums[i] = increasesSums[i - 1] + increases[i];
	}

	Node node;
	node.left = 0;
	node.right = n - 1;
	node.day = 0;
	node.height = 0;
	nodes.push_back(node);

	for (long long i = 0; i < m; ++i) {
		calculateCut();
	}
}