#include <fstream>
#define DIM 100005
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n,m,i,x,v[DIM],tip;
int cb(int x,int tip){
    int st=1,dr=n;
    while(st<=dr){
        int mid=(st+dr)/2;
        if(v[mid]==x){
            if(tip<2)
                st=mid+1;
            else
                dr=mid-1;
        }else
            if(v[mid]<x)
                st=mid+1;
            else
                dr=mid-1;
    }
    if(tip==0&&v[dr]!=x)
        return -1;
    if(tip<2)
        return dr;
    return st;
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    cin>>m;
    for(i=1;i<=m;i++){
        cin>>tip>>x;
        cout<<cb(x,tip)<<'\n';
    }
    return 0;
}