rt

# include <bits/stdc++.h>

# define int long long
# define PII pair <int ,int>

using namespace std;

inline int read(){int s = 0 , w = 0;char c = getchar();while(!isdigit(c)){w |= (c == '-');c = getchar();}while(isdigit(c)){s = (s << 1) + (s << 3) + (c ^ 48);c = getchar();}return w ? -s : s;}
inline void write(int x){if(x < 0) putchar('-') , x = -x;if(x > 9) write(x / 10);putchar(x % 10 | 48);}
inline void writesp(int x){write(x) , putchar(' ');}
inline void writeln(int x){write(x) , putchar('\n');}

# define ls u << 1
# define rs u << 1 | 1
# define inf 1e15
const int N = 3e6 + 10;
int n ,Q;
int a[N] ,pre[N];

struct SGT {int l ,r ,cov ,days ,sum ,mx;}tr[N << 2];

inline void plant (int u ,int days){
  int l = tr[u].l ,r = tr[u].r;
  tr[u].mx += days * a[r];
  tr[u].sum += (pre[r] - pre[l - 1]) * days;
  tr[u].days += days;
} inline void cut (int u ,int val){
  int l = tr[u].l ,r = tr[u].r;
  tr[u].mx = tr[u].cov = val;
  tr[u].sum = val * (r - l + 1);
  tr[u].days = 0;
} inline void pushup (int u){
  tr[u].mx = max (tr[ls].mx ,tr[rs].mx);
  tr[u].sum = tr[ls].sum + tr[rs].sum;
} inline void pushdown (int u){
  if (tr[u].cov != -1){
  	cut (ls ,tr[u].cov) ,cut (rs, tr[u].cov);
  	tr[u].cov = -1;
  } if (tr[u].days){
    plant (ls ,tr[u].days);
    plant (rs ,tr[u].days);
  	tr[u].days = 0;
  }
} inline void build (int u ,int l ,int r){
  tr[u].l = l ,tr[u].r = r;
  tr[u].cov = -1 ,tr[u].sum = tr[u].mx = tr[u].days = 0;
  if (l == r) return;
  int mid = ((l + r) >> 1);
  build (ls ,l ,mid);
  build (rs ,mid + 1 ,r);
  pushup (u);
} inline int search (int u ,int val){
  int l = tr[u].l ,r = tr[u].r;
  pushdown (u);
  if (l == r){
//  	cout << tr[u].sum << ' ' << tr[u].mx << endl; 
  	if (tr[u].mx < val) return inf;
  	return l;
  }
//  pushdown (u);
  int mid = ((l + r) >> 1);
  if (tr[ls].mx >= val) return search (ls ,val);
  else return search (rs ,val);
} inline int cover (int u ,int ql ,int qr ,int val){//区间覆盖 
  int l = tr[u].l ,r = tr[u].r;
  if (l >= ql && r <= qr){
  	int k = tr[u].sum;
  	cut (u ,val);
  	return k - tr[u].sum;
  } 
  pushdown (u);
  int mid = ((l + r) >> 1) ,res = 0;
  if (ql <= mid) res += cover (ls ,ql ,qr ,val);
  if (mid < qr) res += cover (rs ,ql ,qr ,val);
  pushup (u);
  return res;
} signed main (){
  n = read () ,Q = read ();
  for (int i = 1 ; i <= n ; i ++) a[i] = read () ,pre[i] = pre[i - 1] + a[i];
  sort (a + 1 ,a + 1 + n);
  build (1 ,1, n);
  int pred = 0;
  while (Q --){
    int d = read () ,b = read ();
	plant (1 ,d - pred);
	int s = search (1 ,b);
//	cout << s << endl;
	if (s == inf) puts("0");
	else writeln (cover (1 ,s ,n ,b));
	pred = d;
  }
  return 0;
}