#include<fstream>
#include<climits>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001],n,m;

void citire()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    v[n+1]=INT_MAX;
}

int cautb(int t,int x)
{
    int i,s,d,m,ok;
    if(t==0)
    {
        s=1;d=n;
        while(s<d)
        {
            m=(s+d)/2;
            if(v[m]>x)
                d=m;
            else
                s=m+1;
        }
        s=s-1;
        if(x==v[s])
            return s;
        else
            return -1;
    }

    if(t==1)
    {
        s=1;d=n;
        while(s<d)
        {
            m=(s+d)/2;
            if(v[m]>x)
                d=m;
            else
                s=m+1;
        }
        if(v[s]<=x)
            return s;
        else
        return s-1;
    }

    if(t==2)
    {
        s=1;d=n+1;
        while(s<d)
        {
            m=(s+d)/2;
            if(v[m]>x)
                d=m;
            else
                s=m+1;
        }
        s=s-1;
        while(v[s]<x)
            s++;
        return s;
    }
}

int main()
{
    int nr,t,x,i;
    citire();
    fin>>nr;
    for(i=1;i<=nr;i++)
    {
        fin>>t>>x;
        fout<<cautb(t,x)<<'\n';
    }
}