#include <bits/stdc++.h>

using namespace std;

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

const int L=16,NMAX=100001;

int v[NMAX],n,k;

int caut0(int x)
{
    int r=0,pas=1<<L;
    while(pas!=0)
    {
        if(r+pas<=n && v[r+pas]<=x)
        {
            r+=pas;
        }
        pas/=2;
    }
    if(v[r]!=x)
    {
        r=-1;
    }
    return r;
}

int caut1(int x)
{
    int r=0,pas=1<<L;
    while(pas!=0)
    {
        if(r+pas<=n && v[r+pas]<=x)
        {
            r+=pas;
        }
        pas/=2;
    }
    return r;
}

int caut2(int x)
{
    int r=n,pas=1<<L;
    while(pas!=0)
    {
        if(r-pas>=0 && v[r-pas]>=x)
        {
            r-=pas;
        }
        pas/=2;
    }
    return r;
}

int main()
{
    int x,j;
    in>>n;
    for(int i=1;i<=n;++i)
        in>>v[i];
    in>>k;
    for(int i=1;i<=k;++i)
    {
        in>>j>>x;
        if(j==0) out<<caut0(x)<<'\n';
        else if(j==1) out<<caut1(x)<<'\n';
        else out<<caut2(x)<<'\n';
    }
    return 0;
}