#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main()
{
    int n,i,inc,mij,sf,tip,poz0,poz1,poz2,nrintr,nr;
    bool gasit;
    in>>n;
    int x[n+1];
    for(i=1;i<=n;i++) in>>x[i];
    in>>nrintr;
    for(i=1;i<=nrintr;i++)
    {
     in>>tip>>nr;
     if(tip==0)
     {
        poz0=1;
        inc=1; sf=n;
        gasit=0;
        while(inc<=sf)
        {
            mij=(inc+sf)/2;
            if(nr==x[mij])
            {
                if(mij>poz0)poz0=mij;
                gasit=1;
            }
            if(gasit && mij!=poz0) break;
            else
            {
                if(nr>x[mij]) {inc=mij+1;
                                 if(nr<x[inc]) break;}
                else {sf=mij-1;
                      if(nr>x[sf]) break;}
            }
        }
        if(!gasit) out<<"-1\n";
        else out<<poz0<<"\n";
     }
     else if(tip==1)
     {
      poz1=1;
      inc=1; sf=n;
      while(inc<=sf)
        {
            mij=(inc+sf)/2;
            if(nr>=x[mij])
               if(mij>poz1)poz1=mij;
            else
            {
                if(nr>x[mij]) {inc=mij+1;
                                 if(nr<x[inc]) break;}
                else {sf=mij-1;
                      if(nr>x[sf]) break;}
            }
        }
        out<<poz1<<"\n";
     }
     else
     {
      poz2=1;
      inc=1; sf=n;
      while(inc<=sf)
        {
            mij=(inc+sf)/2;
            if(nr<=x[mij])
               if(mij<poz2)poz2=mij;
            else
            {
                if(nr>x[mij]) {inc=mij+1;
                                 if(nr<x[inc]) break;}
                else {sf=mij-1;
                      if(nr>x[sf]) break;}
            }
        }
        out<<poz2<<"\n";
     }
    }
    return 0;
}