#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N,v[500000];

int main()
{
    int i,M,a,b,poz;
    poz=-1;
    f>>N;
    for(i=1; i<=N; i++)
        f>>v[i];

    f>>M;
    for(i=1; i<=M; i++)
    {
        f>>a>>b;

        int mij;
        int st=1;
        int dr=N;
        int ok=0;

        while((ok==0)&&(st<=dr))
        {
            mij=(st+dr)/2;

            if(v[mij]<b)
                st=mij+1;
            else if(v[mij]==b)
                ok=1;
            else if(v[mij]>b)
                dr=mij-1;

        }
        if(a==0)
        {
            while(v[mij]==v[mij+1])
                ++mij;
            if(v[mij]==b)
            g<<mij<<'\n';
            else
            g<<"-1\n";
        }
        else
        if(a==1)
        {
            if(ok)
                dr=mij;
            while(v[dr]==v[dr+1])
                ++dr;
            g<<dr<<'\n';
        }
        else
        {
            if(ok)
                st=mij;
            while(v[st]==v[st-1])
                --st;
            g<<st<<'\n';
        }
    }


    return 0;
}