#include <iostream>
#include <cstdio>

using namespace std;

int s[100005],n,c,x,m;

int caut0(){
    int start,putere;
    for(putere=1;putere<n;putere*=2);
    for(start=0;putere;putere/=2)
        if(start+putere<n && s[start+putere]<=x)
            start+=putere;
    if(s[start]==x)
        return start+1;
    return -1;
}

int caut2(){
    int st = 0, dr = n-1, mij;
    while(st<dr){
        mij=(st+dr)/2;
        if(x<=s[mij])
            dr = mij;
        else
            st = mij+1;
    }
    return st+1;
}

int caut1(){
    int start,putere;
    for(putere=1;putere<n;putere*=2);
    for(start=0;putere;putere/=2)
        if(start+putere<n && s[start+putere]<=x)
            start+=putere;
    return start+1;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    scanf("%d", &n);
    for(int i=0;i<n;++i)
        scanf("%d", &s[i]);
    scanf("%d", &m);
    for(int i=0;i<m;++i){
        scanf("%d%d", &c,&x);
        if(c==0)
            cout<<caut0()<<"\n";
        else if(c==1)
            cout<<caut1()<<"\n";
        else
            cout<<caut2()<<"\n";
    }

    return 0;
}