#include<fstream>

using namespace std;

int v[100001];
int n,m;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int CB0 (int st, int dr, int x)
{
    int mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=x)
            st=mid+1;
        else
            dr=mid-1;
    }
    mid=(st+dr)/2;
    if(v[mid]>x)
        mid--;
    if(v[mid]==x)
        return mid;
    return -1;
}
int CB1 (int st, int dr, int x)
{
    int mid, n=dr;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=x)
            st=mid+1;
        else
            dr=mid;
    }
    mid=(st+dr)/2;
    if(v[mid]>x)
        mid--;
    return mid;
}
int CB2 (int st,int dr,int x)
{
    int mid;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<x)
            st=mid+1;
        else
            dr=mid;
    }
    mid=(st+dr)/2;
    if(v[mid]<x)
        mid++;
    return mid;
}

int main()
{
    int i,nr,x;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>nr>>x;
        if(nr==0)
            fout<<CB0(1,n,x)<<"\n";
        if(nr==1)
            fout<<CB1(1,n,x)<<"\n";
        if(nr==2)
            fout<<CB2(1,n,x)<<"\n";
    }
    return 0;
}