#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream FIN("cautbin.in");
ofstream FOUT("cautbin.out");

const int MAX  = 1e5+1;

// Variabile globale
int N,M;
vector<int> v;
vector< pair<int,int> > cerinte;

void Read()
{
    FIN >> N;
    int x,y,i;
    for(i = 0; i < N; ++i){
        FIN >> x;
        v.push_back(x);
    }
    FIN >> M;
    for(i = 0 ; i < M; ++ i){
        FIN >> x >> y;
        cerinte.push_back(make_pair(x,y));
    }
}

void Cerinta0(int x)
{
    if(!binary_search(v.begin(),v.end(),x))
        FOUT << -1;
    else
    {
        FOUT << upper_bound(v.begin(), v.end(), x) - v.begin();
    }
}
void Cerinta1(int x)
{
    int pas = 1 << 18, i;
    while(pas)
    {
        if(i + pas < v.size())
        {

        }
    }
}
void Cerinta2(int x)
{
    FOUT << upper_bound(v.begin(), v.end(), x) - v.begin();
}

int main()
{
    Read();
    vector< pair <int,int> >::iterator it;
    for(it = cerinte.begin(); it!= cerinte.end(); ++it){
        pair<int, int> result = (*it);
        if(result.first == 0)
            Cerinta0(result.second);
        else if(result.first == 1)
            Cerinta1(result.second);
        else
            Cerinta2(result.second);
        FOUT << endl;
    }
    return 0;
}