#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100100],n,m,a1,a2,sol,t;
void citire()
{
    f>>n;
    for(int i=1;i<=n;i++) f>>a[i];
}
int cautbin_0(int x)
{
    int li=1,lf=n,l;
    while(li<=lf)
    {
        l=(li+lf)/2;
        if(a[l]==x) return l;
        else
        {

            if(x>a[l]) li=l+1;
            if(x<a[l]) lf=l-1;
        }
    }
    return -1;
}
int cautbin_1(int x)
{
    int li=1,lf=n,l;
    while(li<=lf)
    {
        l=(li+lf)/2;
        if(a[l]==x) return l;
        else
        {
            t=0;
            if(x>a[l]) {li=l+1;t=1;}

            if((x<a[l])&&(t==0)) lf=l-1;
        }
    }
    return l;
}
void solve()
{
    f>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a1>>a2;sol=0;
        if(a1==0) {sol=cautbin_0(a2);
        if(sol==-1) g<<-1<<"\n";
        else
        {
        while(a[sol]==a2) sol++;

   g<<sol-1<<"\n";}
        }
        if(a1==1)
        {
           sol=cautbin_1(a2);
    while(a[sol]<=a2) sol++;
    g<<sol-1<<"\n";
        }
       if(a1==2)
        {
            sol=cautbin_1(a2);
            while(a[sol]>=a2) sol--;
        g<<sol+1<<"\n";
        }
    }
}
int main()
{

    citire();
    a[n+1]=2000000000;
    a[0]=-100;
    solve();
    return 0;
}