#include<stdio.h>
using namespace std;
int n,m,i,v[100001],c,e,rez,begin,end;

int comanda0(int ee)
{begin=1; end=n;
int mij;
while(begin<=end)
{mij=(end+begin)/2;
 if(v[mij]<=ee)
    begin=mij+1;
 else 
    end=mij-1;
}
mij=(end+begin)/2;
if(v[mij]==ee)
return mij;   
else
return (mij-1); 
}

int comanda1(int ee)
{begin=1; end=n;
int mij;
while(begin<end)
{mij=(begin+end)/2;
 if(v[mij]<=ee)
    begin=mij+1;
 else 
    end=mij;
}
mij=(end+begin)/2;
if(v[mij]>ee)
  mij--;
return mij;

}

int comanda2(int ee)
{begin=1; end=n;
int mij;
while(begin<end)
{mij=(begin+end)/2;
 if(v[mij]<ee)
    begin=mij+1;
 else 
    end=mij;
}
mij=(end+begin)/2;
if(v[mij]<ee)
  mij++;
return mij;   
}

int main()
{
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for(i=1; i<=n; i++)
  scanf("%d",&v[i]);
scanf("%d",&m);  
for(i=1; i<=m; i++)
 {scanf("%d %d",&c,&e);  
  if(c==0)
     {rez=comanda0(e);
      if(v[rez]==e)
      printf("%d\n",rez);
      else
      printf("-1\n");}
  if(c==1)
     {rez=comanda1(e);  
      printf("%d\n",rez);}  
  if(c==2)
     {rez=comanda2(e);  
      printf("%d\n",rez);}          
  }
return 0;}