#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAX 100000

struct avioane
{
    int p;
    int h;
}av[MAX+1];

bool cmp(avioane i,avioane j)
{
    return i.poz<j.poz;
}

int v[MAX+2];
int dr[MAX+1],st[MAX+1];
int stiva[MAX+1];
int main()
{
    FILE *fin,*fout;

    fin=fopen("avioane.in","r");
    fout=fopen("avioane.out","w");

    int i,j,n,q,inc,sf,pr,ul;

    fscanf(fin,"%i%i",&n,&q);

    for(i=1;i<=n;i++)
        fscanf(fin,"%i",&v[i]);

    v[0]=v[n+1]=1000000001;

    for(i=1;i<=q;i++)
        fscanf(fin,"%i%i",&av[i].p,&av[i].h);

    sort(&av[1],&av[q+1],cmp);

    j=2;
    pr=ul=1;
    stiva[1]=v[1];
    for(i=1;i<=q;i++)
    {
        while(av[i].poz!=j)
        {
            if(v[j]<=stiva[ul])
                stiva[++ul]=v[j];

            else
            {
                while(v[j]>stiva[ul])
                    ul--;
                stiva[++ul]=v[j];
            }
            j++;
        }
    }

    return 0;
}