#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{
    int n,p,k,x,nr=0,ic,ok=0,a[100005],i,l,mx=0,m,v;
    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;
    v=p;
    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) {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;
       ic=0;
       p=v;
    m--;
   }
    return 0;
}