#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,e,a,x[100100],M,l,r,mid;
int ok(int i)
{
    if(a>=x[i])
        return 1;
    else
        return 0;
}
int ok2(int i)
{
    if(a>=x[i])
        return 1;
    else
        return 0;
}
int ok3(int i)
{
    if(a<=x[i])
        return 1;
    else
        return 0;
}
int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>x[i];
    fin>>M;
    for(int i=1; i<=M; i++)
    {

        fin>>e>>a;
        if(e==0)
        {
            l=1;
            r=n;
            while(l!=r)
            {
                mid=(l+r)/2;
                if(ok(mid))
                    l=mid+1;
                else
                    r=mid;
            }
            if(x[mid]==a)
                fout<<l-1;
            else
                fout<<-1;
        }
        else if(e==1)
        {
            l=1;
            r=n;
            while(l!=r)
            {
                mid=(l+r)/2;
                if(ok2(mid))
                    l=mid+1;
                else
                    r=mid;
            }
            fout<<l-1;

        }
        else
        {
            l=1;
            r=n;
            while(l!=r)
            {
                mid=(l+r)/2;
                if(ok3(mid))
                    r=mid;
                else
                    l=mid+1;
            }
            fout<<l;

        }
    }
}