#include <iostream>
#include <bitset>
#include <fstream>

using namespace std;

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



int cer0(int lg,int v[],int n ,int x)
{
    int poz;
    for(poz=0;lg!=0;lg>>=1)
        if(lg+poz<=n && v[lg+poz]<=x)
        poz+=lg;

    if(v[poz]==x)
    return poz;
    return -1;
}

int cer1(int lg,int v[],int n, int x)
{

    int poz;
    for(poz=0;lg!=0;lg>>=1)
        if(lg+poz<=n && v[lg+poz]<=x)
        poz+=lg;



    return poz;
}

int cer2(int lg,int v[],int n, int x)
{
    int poz;
    for(poz=n;lg!=0;lg>>=1)
        if(poz-lg>0 && v[poz-lg]>=x)
        poz-=lg;

    return poz;
}

void citire(int &n, int v[], int k,int &m,int t,int lg)
{
    in>>n;

    for(int i=1;i<=n;i++)
        in>>v[i];

        in>>m;

        while(m)
        {
            in>>t>>k;
            m--;
            if(t==0)
               out<< cer0(lg,v,n,k)<<endl;
            if(t==1)
               out<< cer1(lg,v,n,k)<<endl;
            if(t==2)
               out<< cer2(lg,v,n,k)<<endl;
        }
}
int main()
{

    int lg=1,v[100005],k,m,t,n;
    for(lg;lg<=n;lg<<=1);

    citire(n,v,k,m,t,lg);


    return 0;
}