#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

long long N,x[100001],M,y[100001],z,li,lf,m,ras[100001],i;

int main()
{
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>x[i];
    }
    fin>>M;
    for(i=1;i<=M;i++)
    {
        fin>>y[i]>>z;
        switch(y[i])
        {
            case 0:
                li=1;lf=N;
                m=(li+lf)/2;
                while(li<=lf)
                {
                    if(z>=x[m])
		                li=m+1;
                    else
                        lf=m-1;
                    m=(li+lf)/2;
                }
                if(lf>=1 && x[lf]==z)  ras[i]=lf;
	            else   ras[i]=-1;
	            break;
	        case 2:
	            li=1;lf=N;
                m=(li+lf)/2;
                while(li<=lf)
                {
                    if(z<=x[m])
		                lf=m-1;
                    else
                        li=m+1;
                    m=(li+lf)/2;
                }
                ras[i]=li;
                break;
            case 1:
                li=1;lf=N;
                m=(li+lf)/2;
                while(li<=lf)
                {
                    if(z>=x[m])
		                li=m+1;
                    else
                        lf=m-1;
                    m=(li+lf)/2;
                }
                ras[i]=lf;
	            break;
        }

    }
    for(i=1;i<=M;i++)
    {
        fout<<ras[i]<<'\n';
    }
    return 0;
}