#include <fstream>

using namespace std;
ifstream f("cb.in");
ofstream g("cb.out");

int main()
{
    int n,p,k,x,nr=0,ic,ok=0,a[100005],i,l,mx=0,m;
    f>>n;
    for(i=1;i<=n;i++) f>>a[i];
    x=n;
    while (x!=0)
    {
        x >>= 1;
        nr++;
    }
    p=(1<<nr);
    ic=0;
    p=p/2;
    f>>m;
    while(m)
   {
       f>>l>>k;
       if(l==0)
       {
        while(ok==0&&p)
    {
        if(a[p+ic]==k) {ok=1;if(p+ic>mx)mx=p+ic;}
        else if(a[p+ic]<k) {ic=ic+p;}
        p=p>>1;
    }
    if(ok==1) g<<mx;
    else g<<"-1";
       }
       else if(l==1)
       {
            while(p)
    {
        if(a[p+ic]==k) {}
        else if(a[p+ic]<=k) {ic=ic+p;if(p+ic>mx)mx=p+ic;}
        p=p>>1;
    }
    g<<mx;
       }
       else if(l==2)
       {
           mx=n;
           while(p)
           {
            if(a[p+ic]>=k) {if(p+ic<mx){mx=p+ic;}}
        else if(a[p+ic]<k) {ic=ic+p;}
        p=p>>1;
           }
           g<<mx;
       }
       g<<endl;
    m--;
   }
    return 0;
}