#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<dr){
    mi=st + (dr-st)/2;
    if(a[mi]<x)
    st=mi+1;
    else
    if(a[mi]>x)
        dr=mi-1;
        else
        {
            while(a[mi]==x)
                mi++;
            mi--;
            return mi;
        }
        return -1;
}

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