#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,v[100001],i,j,k,m,p,a,ok;
int cautb0(int s, int d, int val)
{
    int m;
    while(s<=d)
    {
        m=(s+d)/2;
        if(v[m]<=val)
            s=m+1;
        else
            d=m-1;
    }
    m=(s+d)/2;
    if(v[m]>val) m--;
    if(v[m]==val) return m;
    return -1;
}

int cautb1(int s, int d, int val)
{
    int m,n=s;
    while(s<d)
    {
        m=(s+d)/2;
        if(v[m]<=val) s=m+1;
        else d=m;
    }
     m=(s+d)/2;
     if(v[m]>val) m--;
     return m;
}
int cautb2(int s, int d, int val)
{
    int m;
    while(s<d)
    {
        m=(s+d)/2;
        if(v[m]<val) s=m+1;
        else d=m;
    }
    m=(s+d)/2;
    if(v[m]<val)
        m++;
    return m;
}
int main()
{
    in>>n;
    for(i=1;i<=n;i++) in>>v[i];
    ok=1;
    in>>m;
    for(k=1;k<=m;k++)
    {
        in>>p>>a;
        if(p==0) out<<cautb0(ok,n,a)<<"\n";
        else if(p==1) out<<cautb1(ok,n,a)<<"\n";
        else out<<cautb2(ok,n,a)<<"\n";
    }

    return 0;
}