#include<iostream>
#include<fstream>

using namespace std;

int a[100001],n,i,m,mm,o,x;

int sol_0_x(int x){
    int s=0,d=n-1;
    while(s<=d){
        m=(s+d)/2;
        if(a[m]<=x) s=m+1;
        else d=m-1;
    }
    m=(s+d)/2;
    if(a[m] > x) m --;
    if(a[m] == x) return m+1;
    return -1;
}

int sol_1_x(int x){
    int s=0,d=n-1;
    while (s < d){
        m = (s + d) / 2;
        if (a[m] <= x) s = m + 1;
        else d = m;
    }
    m = (s + d) / 2;
    if (a[m] > x) -- m;
    return m+1;
}

int sol_2_x(int x){
    int s=0,d=n-1;
    while (s < d) {
        m = (s + d) / 2;
        if (a[m] < x) s = m + 1;
        else d = m;
    }
    m = (s + d) / 2;
    if (a[m] < x) ++ m;
    return m+1;
}

int main(){
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for(i=0;i<n;i++) f>>a[i];
    //for(i=0;i<n;i++) cout<<a[i]<<" ";
    f>>mm;
    while(mm--){
        f>>o>>x;
        if(o==0) g<<sol_0_x(x)<<"\n";
        else
            if(o==1) g<<sol_1_x(x)<<"\n";
            else g<<sol_2_x(x)<<"\n";
    }
    f.close(); g.close();

    return 0;
}