#include <bits/stdc++.h>
#define DM 100001
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,v[DM],q,x,c;

int sol0(){
    int st=1,dr=n,mid;
    while(dr>st){
        mid=(dr+st+1)/2;
        if(v[mid]>x) dr=mid-1;
        else st=mid;
    }
    if(v[st]!=x) return -1;
    return st;
}
int sol1(){
    int st=1,dr=n,mid;
    while(dr>st){
        mid=(dr+st+1)/2;
        if(v[mid]>x) dr=mid-1;
        else st=mid;
    }
    return st;
}
int sol2(){
    int st=1,dr=n,mid;
    while(dr>st){
        mid=(st+dr)/2;
        if(v[mid]<x) st=mid+1;
        else dr=mid;
    }
    return st;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;++i) fin>>v[i];
    fin>>q;
    while(q--){
        fin>>c>>x;
        if(c==0) fout<<sol0()<<'\n';
        if(c==1) fout<<sol1()<<'\n';
        if(c==2) fout<<sol2()<<'\n';
    }
    return 0;
}