#include <cstdio>

int N,V[100001],M,pow2;

void proc_log()
{
 int log2N=0;
 for(int i=2;i<=N;++i)
  if(!(i&(i-1))) ++log2N;
  pow2 = 1<<log2N;
}

int bsc0(int e)
{
 int i,poww2=pow2;
 if(e<V[1] || e>V[N]) return -1;
 for(i=1;i<=N && poww2; )
   if(V[i+poww2]>e || i+poww2>N) poww2>>=1;
    else i+=poww2;
 if(V[i] == e) return i;
 return -1;
}

int bsc1(int e)
{
 int i,poww2=pow2;
 for(i=1;i<=N && poww2; )
   if(V[i+poww2]>e || i+poww2>N) poww2>>=1;
    else i+=poww2;
 return i;
}

int bsc2(int e)
{
 int i,poww2=pow2;
 for(i=1;i<=N && poww2; )
   if(V[i+poww2]>=e || i+poww2>N) poww2>>=1;
    else i+=poww2;
 if(V[i]==e) return i;
 return i+1;

}

int main()
{
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 scanf("%d",&N);
 proc_log();
 for(int i=1;i<=N;scanf("%d",&V[i++]));
 scanf("%d",&M);
 while(M--)
 {
  int q,p;
  scanf("%d %d",&q,&p);
  switch (q)
  {
  case 0: printf("%d\n",bsc0(p)); break;
  case 1: printf("%d\n",bsc1(p)); break;
  case 2: printf("%d\n",bsc2(p)); break;
  }
 }
 return 0;
}