#include <fstream>

using namespace std;
int a[100005],n,m;

int cb0(int x)
{
    int st=1,dr=n,mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid]<=x && a[mid+1]>x) break;
        else if(a[mid]<=x) st=mid+1;
        else dr=mid-1;
    }
    if(a[mid]==x) return mid;
    return -1;
}

int cb1(int x)
{
    int st=1,dr=n,mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid+1]>x && a[mid]<=x) break;
        else if(a[mid]<=x) st=mid+1;
        else dr=mid-1;
    }
    return mid;
}

int cb2(int x)
{
    int st=1,dr=n,mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid]>=x && a[mid-1]<x) break;
        else if(a[mid]<x) st=mid+1;
        else dr=mid-1;
    }
    return mid;
}

int main()
{
    int ok,x,i;
    ifstream in("cautbin.in");
    in>>n;
    for(i=1;i<=n;i++)
        in>>a[i];
    in>>m;
    ofstream out("cautbin.out");
    for(i=1;i<=m;i++)
    {
        in>>ok>>x;
        if(ok==0) out<<cb0(x)<<"\n";
        if(ok==1) out<<cb1(x)<<"\n";
        if(ok==2) out<<cb2(x)<<"\n";
    }
    in.close();
    out.close();
    return 0;
}