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

int caut0(unsigned int s,unsigned int d)
{
    unsigned int m;
    if(d-s<=1) {if(a[d]==x) return d;
    else {if(a[s]==x) return s; else return -1;}}
    m=(s+d)/2;
    if (x<a[m]) return caut0(s,m-1);
    else if(x>=a[m]) return caut0(m,d);
}
int caut1(unsigned int s,unsigned int d)
{
    unsigned int m;
    if(d-s<=1) {if(a[d]<=x) return d; return s;}
    m=(s+d)/2;
    if (x<a[m]) return caut1(s,m-1);
    else if(x>=a[m]) return caut1(m,d);
}
int caut2(unsigned int s,unsigned int d)
{
    unsigned int m;
    if(d-s<=1) return d;
    m=(s+d)/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");
    unsigned 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;
    }