#include<stdio.h>
#define N 100001
long bin1(long v[N],long p,long q,long x)
{long m=p+(q-p)/2;
if(p>q)
       return -1;
if(v[m]==x)
       {while(v[m+1]==x)
              m++;
       return m;}
if(v[m]<x)
       return bin1(v,m+1,q,x);
else
       return bin1(v,p,m-1,x);}

long bin2(long v[N],long p,long q,long x)
{long m=p+(q-p)/2;
if(v[m]<x)
       if(x<v[m+1])
              return m+1;
       else
              return bin2(v,m+1,q,x);
else
       if(v[m-1]<x)
              return m;
       else
              return bin2(v,p,m-1,x);}

long bin3(long v[N],long p,long q,long x)
{long m=p+(q-p)/2;
if(v[m]<x)
       if(x<v[m+1])
              return m;
       else
              return bin3(v,m+1,q,x);
else
       if(v[m-1]<x)
              return m-1;
       else
              return bin3(v,p,m-1,q);}

long bin4(long v[N],long p,long q,long x)
{long m=p+(q-p)/2;
if(p>q)
       return -1;
if(v[m]==x)
       {while(v[m-1]==x)
              m--;
       return m;}
if(v[m]<x)
       return bin4(v,m+1,q,x);
else
       return bin4(v,p,m-1,x);}

int main()
{long n,m,i,x[N],y[N],v[N];
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
       scanf("%ld",&v[i]);
for(i=1;i<=m;i++)
       {scanf("%ld",&x[i]);
       scanf("%ld",&y[i]);}
for(i=1;i<=m;i++)
if(x[i]==0)
       printf("%ld\n",bin1(v,1,n,y[i]));
else
       if(x[i]==1)
               if(bin1(v,1,n,y[i])!=-1)
                      printf("%ld\n",bin1(v,1,n,y[i]));
               else
                      printf("%ld\n",bin2(v,1,n,y[i]));
       else
               if(bin4(v,1,n,y[i])!=-1)
                      printf("%ld\n",bin4(v,1,n,y[i]));
               else
                      printf("%ld\n",bin3(v,1,n,y[i]));
fclose(stdin);
fclose(stdout);
return 0;}