#include <iostream>
#include <fstream>

using namespace std;

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

int n,m,i,value,question;
int elemente[100000];

int cautbin(int q,int key){

    int st = 1, dr = n,mid;

    if(q == 2){
        while(st < dr){
            mid = st + (dr-st)/2;

            if( elemente[mid] < key)
                st = mid + 1;
            else
                dr = mid;
        }
        if( elemente[mid] < key)
            mid++;
        return mid;
    }
    if(q == 0){
        while(st < dr){
            mid = st + (dr-st)/2;

            if (elemente[mid] <= key)
                    st = mid + 1;
            else
                    dr = mid - 1;
        }
        mid = (st + dr)/2;
        if( elemente[mid] > key)
            mid--;
        if(elemente[mid] == key)
            return mid;
        return -1;
    }
    if(q == 1){
        while(st < dr){
            mid = (st + dr)/2;

            if( elemente[mid] <= key)
                mid = st + 1;
            else
                mid = dr;
        }
        mid = (st+dr)/2;

        if( elemente[mid] > key)
            mid--;
        return mid;
    }
}


int main()
{
    fin>>n;
    for(i = 1;i<=n;i++)
        fin>>elemente[i];
    fin>>m;
    for(i = 1; i<=m;i++){
        fin>>question;
        fin>>value;
        fout<<cautbin(question,value)<<"\n";
    }
    return 0;
}