#include<fstream>

using namespace std;

int N,v[100001];

fstream fin("cautbin.in",ios::in);

fstream fout("cautbin.out",ios::out);


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

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

int c2(int x)
{
    int s=1,c=N,M;
        while(s<c)
        {
            M=(s+c)/2;
            if (v[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>>v[i];
        fin>>t;
    for(i=1;i<=t;i++)
        {
            fin>>k>>x;
            switch(k)
            {
                case 0: fout<<c0(x)<<'\n'; break;
                case 1: fout<<c1(x)<<'\n'; break;
                case 2: fout<<c2(x)<<'\n';
            }
        }

    fin.close();

    fout.close();

    return 0;
}