#include <iostream>
#include <fstream>
using namespace std;
long a[100000];

long cautare(long x,long n)
{long k, pos=1<<30;
    for (k=0;pos!=0;pos=pos/2)
        if (k+pos<=n && a[k+pos]<x) k+=pos;
    return k+1;
    
}

int main()
{
    long n,i,m,x,y,l,o;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for (i=1;i<=n;i++) f>>a[i];
    f>>m;
    for (i=1;i<=m;i++)
    {f>>x>>y;
       long  k=cautare(y,n);

        if (a[k]==y)
        {if (k==n && x!=2) g<<k<<"\n";
        else {
        for (l=k;l<n;l++) if (a[l]!=y) break;
        for (o=k;o>-1;o--) if (a[o]!=y) break;
            if (x==2) g<<o+1<<"\n";
            else g<<l-1<<"\n";}}
        else
        { if (k>n)
        {if (x==0) g<<-1<<"\n";
            else g<<k-1<<"\n";
        }
         else if  (a[k]<y)
        {if (x==0) g<<-1<<"\n";
             else if (x==1) g<<k<<"\n";
            else g<<k+1<<"\n";
                   }
        else
        { if (x==0) g<<-1<<"\n";
            else if (x==1) g<<k-1<<"\n";
            else g<<k<<"\n";
        }
        }}
    f.close();
    g.close();
    return 0;
}