#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");
int n,c,nn,x,a[100010],i,r,nr;
int caut(int x)
{
    int st,dr,m;
    st=1;
    dr=n;
    while(st<=dr)
    {
        m= st + (dr-st)/2;
        if(a[m]<=x)st=m+1;
        else dr=m-1;
    }
    m = st + (dr-st)/2;
    if(a[m]>x)m--;
    if(a[m]==x)return m;
    return -1;
}
int caut2(int x)
{
    int st,dr,m;
    st=1;
    dr=n;
    while(st<=dr)
    {
        m=st+(dr-st)/2;
        if(a[m]>=x)dr=m-1;
        else st=m+1;
    }
    m=st+(dr-st)/2;
    if(a[m]<x)m++;
    if(a[m]==x)return m;
    return -1;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i];
    }
    f>>nn;
    for(i=1;i<=nn;i++)
    {
        f>>c;
        f>>nr;
        if(c==0)
        {
            r=caut(nr);
            g<<r<<"\n";
        }
        if(c==1)
        {
             r=caut(nr);
             while(r==-1)
             {
                 x--;
                 r=caut(nr);
             }
             g<<r<<"\n";
        }
        if(c==2)
        {
            r=caut2(nr);
            while(r==-1)
            {
                x--;
                r=caut2(nr);
            }
            g<<r<<"\n";
        }
    }
    return 0;
}