#include <fstream>
#include <iostream>

using namespace std;

ifstream a("cautbin.in");
ofstream b("cautbin.out");

int n,m,v[100001],p,x;

int cautbin0(int fx,int lx,int x)
{
    int f=fx;
    int l=lx;

    while(l-f>1)
    {
        int m=(f+l)>>1;
        if(x<v[m])
            l=m-1;
        else f=m;
    }
    if(v[l]==x)return l;
    else if(v[f]==x)return f;
    else return -1;
}

int cautbin1(int fx,int lx,int x)
{
    int f=fx;
    int l=lx;

    while(l-f>1)
    {
        int m=(f+l)>>1;
        if(x<v[m])l=m-1;
        else f=m;
    }
    if(v[l]<=x)return l;
    else if(v[f]<=x)return f;
}


int cautbin2(int fx,int lx,int x)
{
    int f=fx;
    int l=lx;

    while(l-f>1)
    {
        int m=(f+l)>>1;
        if(v[m]<x)f=m+1;
        else l=m;
    }
    if(v[f]>=x)return f;
    else if(v[l]>=x)return l;
}

int main()
{
    a>>n;
    for(int i=1;i<=n;i++)
    a>>v[i];

    a>>m;
    for(int i=1;i<=m;i++)
    {
        a>>p>>x;
        int c=0;
        if(p==0)c=cautbin0(1,n,x);
        else if(p==1)c=cautbin1(1,n,x);
        else if(p==2)c=cautbin2(1,n,x);

        b<<c<<endl;
    }

    return 0;
}