#include <fstream>
#include <algorithm>
using namespace std;
int v[100005], inceput[100005], terminat[100005];
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int main()
{
    int n;
    cin>>n;
    cin>>v[1];
    inceput[v[1]]=1;
    for(int i=2; i<=n; i++){
        cin>>v[i];
        if(v[i]!=v[i-1]){
            inceput[v[i]]=i+1;
            terminat[v[i-1]]=i;
        }
    }
    int k, a, b;
    cin>>k;
    for(int i=0; i<k; i++){
        cin>>a>>b;
        if(a==0 && terminat[b]>0) cout<<terminat[b] - 1<<"\n";
        else if(a==0 && terminat[b]==0) cout<<"-1"<<"\n";
        else if(a==1 && inceput[b]!=0)cout<<terminat[b] - 1<<"\n";
        else if(a==1 && inceput[b]==0) cout<<*lower_bound(v+1, v+n+1, b) - 1<<"\n";
        else if(a==2 && inceput[b]!=0) cout<<inceput[b] - 1<<"\n";
        else if(a==2 && inceput[b]==0) cout<<*upper_bound(v+1, v+n+1, b) - 1<<"\n";
    }
}