#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;
}


int main()
{
    int lg=1,v[100000],k,m,t,n;

        in>>n;

        for(lg;lg<=n;lg<<=1);
    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)<<"\n";
            if(t==1)
               out<< cer1(lg,v,n,k)<<"\n";
            if(t==2)
               out<< cer2(lg,v,n,k)<<"\n";
        }





    return 0;
}