#include <iostream>
#include <fstream>
#define nmax 100099
using namespace std;
int n,v[nmax];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int cauta0(int x)
{int st,dr,mij;
st=1,dr=n;

    while(st<=dr)
    {mij=(st+dr)/2;

     if(v[mij]<=x){st=mij+1;}
     else dr=mij-1;
    }
    if(v[dr]==x)return dr;
    else return -1;
}

int cauta1(int x)
{int st,dr,mij;
st=1,dr=n;

    while(st<=dr)
    {mij=(st+dr)/2;

     if(v[mij]<=x){st=mij+1;}
     else dr=mij-1;
    }
    return dr;
}

int cauta2(int x)
{int st,dr,mij;
st=1,dr=n;

    while(st<=dr)
    {mij=(st+dr)/2;

     if(x<=v[mij]){dr=mij-1;}
     else st=mij+1;
    }
    return st;
}

int main()
{int i,x,y,t;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
fin>>t;
while(t--)
{fin>>x>>y;
if(x==0){fout<<cauta0(y);}
else if(x==1){fout<<cauta1(y);}
else fout<<cauta2(y);
}
}