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
#include<cstdio>
#include<algorithm>
#define e1 first
#define e2 second
using namespace std;

long long sp,kp,pp,dp,lz,ss;
long long zs,h,t1[1000000],d,t[1000000];
pair<pair<long long,long long>,pair<long long,long long> > stc[1000000];

bool can(){if(ss==0) return false;return h<=stc[ss-1].e2.e2+t[stc[ss-1].e1.e1]*(d-stc[ss-1].e2.e1);}

void push(pair<pair<long long,long long>,pair<long long,long long> > e){stc[ss]=e;ss++;}

int main()
{
	scanf("%lld%lld",&dp,&lz);
	for(long long i=1;i<=dp;i++)scanf("%lld",&t[i]);
	sort(t+1,t+dp+1);
	for(long long i=1;i<=dp;i++)t1[i]=t1[i-1]+t[i];
	push(make_pair(make_pair(1,dp),make_pair(0,0)));
	for(long long i=0;i<lz;i++)
	{
		scanf("%lld%lld",&d,&h);
		zs=0;
		while(can())
		{
			pair<pair<long long,long long>,pair<long long,long long> > p1=stc[ss-1];
			zs+=(p1.e1.e2-p1.e1.e1+1)*(p1.e2.e2-h)+(t1[p1.e1.e2]-t1[p1.e1.e1-1])*(d-p1.e2.e1);
			ss--;
		}
		if(ss!=0)
		{
			pair<pair<long long,long long>,pair<long long,long long> > p1=stc[ss-1];
			pp=p1.e1.e1;kp=p1.e1.e2+1;
			while(pp!=kp)
			{
				sp=((pp+kp)>>1);
				if(h>p1.e2.e2+t[sp]*(d-p1.e2.e1))pp=sp+1;
				else kp=sp;
			}
			stc[ss-1].e1.e2=pp-1;
			if(pp!=p1.e1.e2+1)zs+=(p1.e1.e2-pp+1)*(p1.e2.e2-h)+(t1[p1.e1.e2]-t1[pp-1])*(d-p1.e2.e1);
			if(pp!=dp+1)push(make_pair(make_pair(pp,dp),make_pair(d,h)));
		}
		else
		{
			push(make_pair(make_pair(1,dp),make_pair(d,h)));
		}
		printf("%lld\n",zs);
	}
}