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

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

int n,v[100006];

int cautbin1(int x){
    int p;
    for(p=1;p<=n;p*=2)
    {}
    p/=2;
    int sol=0;
    for(;p>=1;p/=2)
        if(sol+p<=n && v[sol+p]<=x)
            sol=sol+p;
    if(v[sol]==x)
        return sol;
    else return -1;
}

int cautbin2(int x){
    int p;
    for(p=1;p<=n;p*=2)
    {}
    p/=2;
    int sol;
    for(sol=n;p>=1;p/=2)
        if(sol-p>0 && v[sol-p]>=x)
            sol=sol-p;
    return sol;
}

int cautbin3(int x){
    int p;
    for(p=1;p<=n;p*=2)
    {}
    p/=2;
    int sol=0;
    for(;p>=1;p/=2)
        if(sol+p<=n && v[sol+p]<=x)
            sol=sol+p;
    return sol;
}

int main()
{
    int m,x,opt;
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(int i=1;i<=m;i++){
        in>>opt>>x;
        if(opt==0)
            out<<cautbin1(x)<<'\n';
        else if(opt==1)
            out<<cautbin2(x)<<'\n';
        else out<<cautbin3(x)<<'\n';
    }

    return 0;
}