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
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int base=524288;
long long int n, m, drz[2000009], po, ko, sr, akt, pom, a, wyn, wys, czas, ost, pre[500009], x, t;
stack<pair<long long int, long long int> >stos;
vector<pair<long long int, long long int> >s;
vector<long long int>v;
bool spr(long long int a)
{
	akt=a+base;
	pom=0;
	while(akt>0)
	{
		pom=max(pom, drz[akt]);
		akt/=2;
	}
	wys=s[pom].second+v[a]*(t-s[pom].first);
	if(wys>=x)return true;
	return false;
}
void dod(int po, int ko, long long int x)
{
	po+=base;
	ko+=base;
	while(po<ko)
	{
		if(po%2==0)po/=2;
		else
		{
			drz[po]=x;
			po=po/2+1;
		}
		if(ko%2==1)ko/=2;
		else
		{
			drz[ko]=x;
			ko=ko/2-1;
		}
	}
	if(po==ko)drz[po]=x;
}
int main()
{
	scanf("%lld %lld", &n, &m);
	for(int p=0; p<n; p++)
	{
		scanf("%lld", &a);
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	pre[0]=v[0];
	for(int p=1; p<v.size(); p++)
	{
		pre[p]=pre[p-1]+v[p];
	}
	s.push_back(make_pair(0, 0));
	stos.push(make_pair(0, 0));
	for(int p=1; p<=m; p++)
	{
		scanf("%lld %lld", &t, &x);
		s.push_back(make_pair(t, x));
		po=0;
		ko=n-1;
		while(po<ko)
		{
			sr=(po+ko)/2;
			if(spr(sr)==true)ko=sr;
			else po=sr+1;
		}
		akt=po+base;
		pom=0;
		while(akt>0)
		{
			pom=max(pom, drz[akt]);
			akt/=2;
		}
		wys=s[pom].second+v[po]*(t-s[pom].first);
		//printf("%lld\n", pom);
		if(wys<x)printf("0\n");
		else
		{
			wyn=0;
			ost=n-1;
			while(stos.top().second>po)
			{
				czas=s[stos.top().first].first;
				wys=s[stos.top().first].second;
				wyn+=(t-czas)*(pre[ost]-pre[stos.top().second-1])-((ost-stos.top().second+1)*(x-wys));
				ost=stos.top().second-1;
				stos.pop();
			}
			if(po!=0)
			{
				czas=s[stos.top().first].first;
				wys=s[stos.top().first].second;
				//printf("%d %d %d\n", pre[ost], pre[po-1], x);
				wyn+=(t-czas)*(pre[ost]-pre[po-1])-((ost-po+1)*(x-wys));
			}
			else
			{
				czas=s[stos.top().first].first;
				wys=s[stos.top().first].second;
				//printf("%lld %lld %lld\n", po, czas, wys);
				wyn+=(t-czas)*(pre[ost])-((ost-po+1)*(x-wys));
			}
			stos.push(make_pair(p, po));
			//printf("%d %d\n", p, po);
			dod(po, n, p);
			printf("%lld\n", wyn);
		}
	}
	return 0;
}