#include <fstream>
#include <algorithm>
#define N 100010
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,i,x[N],cod,val,L,R,M;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>x[i];
    fin>>m;
    for(;m;m--)
    {
        fin>>cod>>val;
        if(cod==0)
        {
            L=0;R=n+1;
            while(L!=R-1)
            {
                M=(L+R)/2;
                if(x[M]<=val)L=M;
                else R=M;
            }
            if(x[L]==val)
                fout<<L<<'\n';
            else
                fout<<"-1\n";
        }
        else
        if(cod==1)
        {
            L=0;R=n+1;
            while(L!=R-1)
            {
                M=(L+R)/2;
                if(x[M]<=val)L=M;
                else R=M;
            }
            fout<<L<<'\n';
        }
        else
        {
            L=0;R=n+1;
            while(L!=R-1)
            {
                M=(L+R)/2;
                if(x[M]>=val)R=M;
                else L=M;
            }
            fout<<R<<'\n';
        }
    }
    return 0;
}