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

using namespace std;

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


int tip0(int a[100000],int n,int x,int lg)
{
    int poz;
    for(poz=0;lg!=0;lg>>=1)
        if(lg+poz<=n && a[lg+poz]<=x)
            poz+=lg;
    if(a[poz]==x) return poz;
    return -1;
}

int tip1(int a[100000],int n,int x,int lg)
{
    int poz;
    for(poz=0;lg!=0;lg>>=1)
        if(lg+poz<=n && a[lg+poz]<=x)
            poz+=lg;
    if(a[poz]<=x) return poz;
    return -1;
}

int tip2(int a[100000],int n,int x,int lg)
{
    int poz;
    for(poz=n;lg!=0;lg>>=1)
        if(poz-lg>0 && a[poz-lg]>=x)
            poz-=lg;
    if(a[poz]>=x) return poz;
    return -1;
}

int main()
{
    int a[100000] ,n, m, t, x;

    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    int lg=1;
    for(lg;lg<=n;lg<<=1);
    for(int j=1;j<=m;j++){
        fin>>t>>x;
        if(t==0){
            fout<<tip0(a,n,x,lg)<<"\n";
        }
        if(t==1){
            fout<<tip1(a,n,x,lg)<<"\n";
        }
        if(t==2){
            fout<<tip2(a,n,x,lg)<<"\n";
        }

    }

    return 0;
}