#include<iostream>
#include<fstream>
using namespace std;
long a[100000],x;
int n,m,k;

int caut0(int s,int d)
{
    long m;
    if(d-s<=1) {if(a[d]==x) return d;
    else {if(a[s]==x) return s; else return -1;}}
    m=s+(d-s)/2;
    if (x<a[m]) return caut0(s,m-1);
    else if(x>=a[m]) return caut0(m,d);
}
int caut1(int s,int d)
{
    long m;
    if(d-s<=1) {if(a[d]<=x) return d; return s;}
    m=s+(d-s)/2;
    if (x<a[m]) return caut1(s,m-1);
    else if(x>=a[m]) return caut1(m,d);
}
int caut2(int s,int d)
{
    long m;
    if(d-s<=1) {if(a[s]>=x) return s;
                if(a[d]<=x) return d;
                }
    m=s+(d-s)/2;
    if (x<=a[m]) return caut2(s,m);
    else if(x>a[m]) return caut2(m+1,d);
}


int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int i,j;
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    f>>m;
    for(j=1;j<=m;j++)
        {f>>k>>x;
        if(k==0) g<<caut0(1,n)<<"\n";
        else if(k==1) g<<caut1(1,n)<<"\n";
        else g<<caut2(1,n)<<"\n";}

    f.close();
    g.close();
    return 0;
    }