#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");
int n,a[100001],i,m,c,nr,t;
int cautbin0 (int x){
long long st=1,dr=n,mi;
while(st+1<dr){
    mi=st + (dr-st)/2;
    if(a[mi]<x)
    st=mi+1;
    else
    if(a[mi]>x)
        dr=mi-1;
        else
     st=mi;

}
while(a[st+1]==x)
    st++;
if(a[st]==x)
    return st;
return -1;
}
int cautbin1(int x){
    long long st=1,dr=n,mi;
while(st+1<dr){
    mi=st + (dr-st)/2;
    if(a[mi]<x)
    st=mi+1;
    else
    if(a[mi]>x)
        dr=mi-1;
        else
        dr=mi;
}

while(a[dr]>x)
    dr--;

    return dr;
}
int cautbin2(int x){
 long long st=1,dr=n,mi;
while(st+1<dr){
    mi=st + (dr-st)/2;
    if(a[mi]<x)
    st=mi+1;
    else
    if(a[mi]>x)
        dr=mi-1;
        else
        dr=mi;
}
while(a[dr]<x)
    dr++;
if(a[dr]>=x)
  {while(a[dr]>=x)
    dr--;
    dr++;
    }
        return dr;
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
    fin>>a[i];
fin>>m;
for(i=1;i<=m;i++){
    fin>>c>>nr;
      if(c==0)
        t=cautbin0(nr);
      else
        if(c==1)
     t=cautbin1(nr);
      else t=cautbin2(nr);
  fout<<t<<"\n";
}
}