#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100005],n,m;
int Cbin(int x)
{ int l=1,r=n,mid=0;
   while(l<=r)
   { mid=(l+r)/2;
     if (x>=a[mid]) l=mid+1; else r=mid-1;
   }
   mid=(l+r)/2;
   if (a[mid]>x) mid--;
   if (a[mid]==x) return mid;
return -1;
}
int Cbin2(int x)
{ int l=1,r=n,mid=0;
   while(l<r)
   { mid=(l+r)/2;
     if (x>=a[mid]) l=mid+1; else r=mid-1;
   }
   mid=(l+r)/2;
   if (x<a[mid]) mid--;
return mid;
}
int Cbin3(int x)
{ int l=1,r=n,mid=0;
   while(l<r)
   { mid=(l+r)/2;
     if (x>a[mid]) l=mid+1; else r=mid;
   }
   mid=(l+r)/2;
   if (x>a[mid]) mid++;
return mid;
}

int main()
{ int i,tip,nr;
   f>>n;
   for(i=1;i<=n;i++) f>>a[i];
    f>>m;
    for(i=1;i<=m;i++)
    {f>>tip>>nr;
    if (tip==0) g<<Cbin(nr)<<"\n";
    if (tip==1) g<<Cbin2(nr)<<"\n";
    if (tip==2) g<<Cbin3(nr)<<"\n";
    }
    return 0;
}