#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
//#define fout cout
using namespace std;

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

int n,i,m,k,a;

int main()
{
    fin>>n;
    vector<int> v(n);

    for(auto &b : v)
        fin>>b;

    fin>>m;

    vector<int>::iterator t;

    for(i=1;i<=m;i++)
    {
        fin>>k>>a;
        if(k==2)
        {
            t=lower_bound (v.begin(), v.end(), a);
            fout<<t-v.begin()+1<<"\n";
        }
        if(k==1)
        {
            t=upper_bound (v.begin(), v.end(), a);
            fout<<t-v.begin()<<"\n";
        }
        if(k==0)
        {
            if(binary_search (v.begin(), v.end(), a))
               {
                    t=upper_bound (v.begin(), v.end(), a);
                    fout<<t-v.begin()<<"\n";
               }
            else fout<<-1<<"\n";

        }
    }
}