#include <iostream>
#include <fstream>
using namespace std;
int v[100102],N;
int checkup(int x)
{
    int s;
    s=x;
    while(v[s]==v[x])
    {
        s++;
    }
    return s-1;
}
int checkdown(int x)
{
    int s;
    s=x;
    while(v[s]==v[x])
    {
        s--;
    }
    return s+1;
}
int t1(int x)
{
    int i,mij,li=1, ls=N,found=0;
    while (li<=ls)
    {
        mij=li + (ls-li)/2;
        if (v[mij]==x)
        {
            found=1;
            i=mij;
            while(v[mij]==v[i])
            {
                i++;
            }
            return i-1;
        }
        if (v[mij]>x) ls=mij-1;
        if (v[mij]<x) li=mij+1;
    }
    return -(ls);

}
int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    in>>N;
    int i,t,x,d,M,u;
    for(i=1; i<=N; i++)
    {
        in>>v[i];
    }
    in>>M;
    for(i=1; i<=M; i++)
    {
        in>>t>>x;
        u=t1(x);
        cout<<u;
        if (u==0) int ll;
        if (t==0)
        {
            if (u<0) out<<"-1";
            else out<<u;

        }
        if (t==1)
        {
            if (u<0) out<<-u;
            else out<<u;
        }
        if (t==2)
        {
            if (u<0) out<<checkdown(-u+1);
            else
            {

                d=u;
                while(v[d]==v[u])
                {
                    d--;
                }
                out<<d+1;
            }

        }
        out<<'\n';
    }
    return 0;
}