#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int op,p,ps,pd,a[100001],i,n,y,x,m;
int cautare_bin1(int x){//returneaza poz elementului x daca exista in sir
  int st,dr,k,mid;         //sau poz elementului mai mare ca x daca x nu exista in sir
   st=1; dr=n; k=0;
   while(st<=dr){
       mid=(st+dr)/2;
       if(a[mid]==x)return mid;
       if (a[mid]>x) dr=mid-1;
       else st=mid+1;
        }
   return dr;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)f>>a[i];
    f>>m;
    for(i=1;i<=m;i++){
      f>>op>>y;
      p=cautare_bin1(y);
      pd=p;ps=p;

      if(a[p]==y){
         while(a[pd]==y)pd++;
         while(a[ps]==y)ps--;
         if(op==0)  g<<--pd<<'\n';
         if(op==1)  g<<--pd<<'\n';
         if(op==2)  g<<++ps<<'\n';
      }
      if(a[p]!=y){
         if(op==0)  g<<-1<<'\n';
         if(op==1)if(y>a[p])  g<<p<<'\n';else g<<--p<<'\n';
         if(op==2)  if(y>a[p])  g<<p+1<<'\n';else g<<p<<'\n';
      }
    }
    f.close();g.close();
    return 0;
}