#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100010],i,j,n,k,x,m;

int ana(int v[],int n,int x){
    int p=1,u=n,mid;
    while(p<=u){
        mid=(p+u)/2;
        if(v[mid]<=x)
            p=mid+1;
        else
            u=mid-1;
    }
    if(v[u]==x)
        return u;
    else
        return -1;
}

int mara(int v[],int n,int x){
    int p=1,u=n,mid;
    while(p<=u){
        mid=(p+u)/2;
        if(v[mid]<=x)
            p=mid+1;
        else
            u=mid-1;
    }
    return u;
}

int dana(int v[],int n,int x){
    int p=1,u=n,mid;
    while(p<=u){
        mid=(p+u)/2;
        if(v[mid]<=x)
            p=mid+1;
        else
            u=mid-1;
    }
    return p;
}

int lara(int v[],int n,int x){
    int p=1,u=n,mid;
    while(p<=u){
        mid=(p+u)/2;
        if(v[mid]>=x)
            u=mid-1;
        else
            p=mid+1;
    }
    return p;
}

int main(){
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(j=0;j<m;j++){
        fin>>i>>x;
        if(i==0)
            fout<<ana(v,n,x)<<"\n";
        if(i==1)
            fout<<mara(v,n,x)<<"\n";
        if(i==2)
            fout<<lara(v,n,x)<<"\n";
    }

    return 0;
}