#include <iostream>
#include <fstream>
using namespace std;
int n,i,a[100001],m,x,y,st,dr,nr,j,ok;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
void f()
{
     while(st<=dr)
        {
            nr=st+(dr-st)/2;
            if(x==0&&a[nr]==y)
            {
                ok=1;
                for(j=nr;j<=n;j++)
                    {
                        if(a[j]!=y)
                        {
                            out<<j-1<<"\n";
                            break;
                        }
                    }
                if(j==n+1)
                    out<<n<<"\n";
            }
            if(x==1)
            {
                if(a[nr]<=y&&(a[nr+1]>y||a[nr+1]==0))
                    out<<nr<<"\n";
            }
            if(x==2)
            {
                if(a[nr]>=y&&a[nr-1]<y)
                    out<<nr<<"\n";
            }

            if(a[nr]>=y)dr=nr-1;
            else st=nr+1;
        }
}
int main()
{
    in>>n;
    for(i=1;i<=n;i++)
        in>>a[i];
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y;
        st=1;
        dr=n;
        ok=0;
        f();
        if(x==0&&ok==0)
            out<<"-1"<<"\n";
    }
    in.close();
    out.close();
    return 0;
}