#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N=;

int n,m;

ll a[N],d[N],b[N];

struct Segment_Tree{

#define lson (o<<1)

#define rson (o<<1|1)

    ll addv[N<<],sumv[N<<],suma[N<<],maxv[N<<],setv[N<<];

    inline void pushup(int o){

        sumv[o]=sumv[lson]+sumv[rson];

        maxv[o]=max(maxv[lson],maxv[rson]);

    }

    inline void pushdown(int o,int l,int r){

        int mid=(l+r)>>;

        if(setv[o]!=-){

            maxv[lson]=setv[o];maxv[rson]=setv[o];

            setv[lson]=setv[o];setv[rson]=setv[o];

            sumv[lson]=1LL*setv[o]*(mid-l+);

            sumv[rson]=1LL*setv[o]*(r-mid);

            addv[lson]=;addv[rson]=;setv[o]=-;

        }

        if(addv[o]){

            sumv[lson]+=addv[o]*suma[lson];sumv[rson]+=addv[o]*suma[rson];

            maxv[lson]+=1LL*a[mid]*addv[o];maxv[rson]+=1LL*a[r]*addv[o];

            addv[lson]+=addv[o];addv[rson]+=addv[o];

            addv[o]=;

        }

    }

    inline void build(int o,int l,int r){

        setv[o]=-;

        if(l==r){suma[o]=a[l];return;}

        int mid=(l+r)>>;

        build(lson,l,mid);build(rson,mid+,r);

        suma[o]=suma[lson]+suma[rson];

    }

    ll find(int o,int l,int r,ll v){

        if(l==r){if(maxv[o]>=v)return l;else return -;}

        pushdown(o,l,r);

        int mid=(l+r)>>;

        if(maxv[lson]>=v)return find(lson,l,mid,v);else return find(rson,mid+,r,v);

    }

    ll querysum(int o,int l,int r,int ql,int qr){

        if(ql<=l&&r<=qr)return sumv[o];

        pushdown(o,l,r);int mid=(l+r)>>;;ll ans=;

        if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);

        if(qr>mid)ans+=querysum(rson,mid+,r,ql,qr);

        return ans;

    }

    inline void change(int o,int l,int r,int ql,int qr,ll v){

        if(ql<=l&&r<=qr){

            maxv[o]=setv[o]=v;sumv[o]=1LL*v*(r-l+);

            addv[o]=;return;

        }

        pushdown(o,l,r);int mid=(l+r)>>;

        if(ql<=mid)change(lson,l,mid,ql,qr,v);

        if(qr>mid)change(rson,mid+,r,ql,qr,v);

        pushup(o);

    }

}T;

inline ll read(){

    ll f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    n=read();m=read();

    for(int i=;i<=n;i++)a[i]=read();

    sort(a+,a+n+);

    T.build(,,n);

    for(int i=;i<=m;i++){

        d[i]=read();b[i]=read();

        T.sumv[]+=T.suma[]*(d[i]-d[i-]);T.maxv[]+=1LL*a[n]*(d[i]-d[i-]);

        T.addv[]=d[i]-d[i-];ll t=T.find(,,n,b[i]);

        if(t==-){puts("");continue;}

        ll ans1=T.querysum(,,n,t,n);T.change(,,n,t,n,b[i]);

        ll ans2=T.querysum(,,n,t,n);printf("%lld\n",ans1-ans2);

    }

}