#include <iostream>
#include <fstream>

using namespace std;

int f1(int N,int a[],int x){
    int p=-1;
    for(int i=N/2+1;i<=N;i++){
        if(a[i]==x) p=i;
    }
    if(p!=-1) return p;
    else{
        for(int i=N/2;i>=1;i--){
            if(a[i]==x) return i;
        }
    }
    return p;
}

int f2(int N,int a[],int x){
    int p=0;
    for(int i=N/2+1;i<=N;i++){
        if(a[i]<=x) p=i;
    }
    if(p!=0) return p;
    else{
        for(int i=N/2;i>=1;i--){
            if(a[i]==x) return i;
        }
    }
    return p;
}
int f3(int N,int a[],int x){
    int p=-1;
    for(int i=1;i<=N/2;i++){
        if(a[i]>=x) return i;
    }
    for(int i=N/2+1;i<=N;i++){
        if(a[i]>=x) return i;
    }
    return p;
}


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

int main()
{
    int N,M,c,x;
    fin>>N;
    int a[100000];
    for(int i=1;i<=N;i++){
        fin>>a[i];
    }
    fin>>M;
    while(fin>>c>>x){ 
        if(c==0) fout<<f1(N,a,x)<<endl;
        else if(c==1) fout<<f2(N,a,x)<<endl;
        else fout<<f3(N,a,x);
    }
    return 0;
}