#include<fstream>
#include<iostream>
using namespace std;

int N,a[100001];
fstream fin("cautbin.in",ios::in);
fstream fout("cautbin.out",ios::out);


int cifbin_0(int x)
{
    int s=1,c=N,M;
        while(s<c)
        {
            M=(s+c+1)/2;
            if (a[M]<=x) s=M;
            else c=M-1;
        }
    if(a[s]==x)return s;
    return -1;
}
int cifbin_1(int x)
{
    int s=1,c=N,M;
        while(s<c)
        {

            M=(s+c+1)/2;
            if (a[M]<=x) s=M;
            else c=M-1;
        }
    return s;
}

int cifbin_2(int x)
{
    int s=1,c=N,M;
        while(s<c)
        {
            M=(s+c)/2;
            if (a[M]>=x) c=M;
            else s=M+1;
        }
    return s;
}

int main()
{
    int i,t,k,x;
    fin>>N;
    for(i=1;i<=N;i++)
        fin>>a[i];
        fin>>t;
    for(i=1;i<=t;i++)
        {
            fin>>k>>x;
            switch(k)
            {
                case 0: fout<<cifbin_0(x)<<'\n'; break;
                case 1: fout<<cifbin_1(x)<<'\n'; break;
                case 2: fout<<cifbin_2(x)<<'\n';
            }
        }

    fin.close();

    fout.close();

    return 0;
}