#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 = 0;
    int aux[MAX];
    for(i = 0 ; i< v.size(); i++)
        aux[i + 1] = v[i];
    int n = v.size();
    i = 0;
    while(pas)
    {
        if(i + pas <= n)
        {
            if(aux[i + pas] <= x)
            {
                i+=pas;
            }
        }
        pas>>= 1;
    }
    FOUT <<  i;
}
void Cerinta2(int x)
{
    FOUT << upper_bound(v.begin(), v.end(), x - 1) - v.begin() + 1;
}

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;
}