#include <fstream>

using namespace std;
ifstream fi("cautbin.in");
ofstream fo("cautbin.out");
int n,q;
int A[100001];
int tip,x;
int cautbin1(int val)
{
    int st=1,dr=n;
    while(st<dr)
    {
        int mid=(st+dr+1)/2;
        if(A[mid]<=val)
            st=mid;
        else
            dr=mid-1;
    }
    if(A[st]==val)
        return st;
    else
        return -1;
}
int cautbin2(int val)
{
    int st=1,dr=n;
    while(st<dr)
    {
        int mid=(st+dr+1)/2;
        if(A[mid]<=val)
            st=mid;
        else
            dr=mid-1;
    }
    return st;
    return 0;
}
int cautbin3(int val)
{
    int st=1,dr=n;
    while(st<dr)
    {
        int mid=(st+dr)/2;
        if(A[mid]>=val)
            dr=mid;
        else
            st=mid+1;
    }
    return st;
    return 0;
}
int main()
{
    fi>>n;
    for(int i=1;i<=n;i++)
        fi>>A[i];
    fi>>q;
    for(int i=1;i<=q;i++)
    {
        fi>>tip>>x;
        if(tip==0)
            fo<<cautbin1(x)<<"\n";
        else
        if(tip==1)
            fo<<cautbin2(x)<<"\n";
        else
            fo<<cautbin3(x)<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}