//cautare binara cu upper si lower
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
constexpr int NX = 100010;
int v[NX];
int main()
{
    int N, M, x, y;
    fin>>N;
    for(int i=1; i<=N; ++i)
        fin>>v[i];

    fin>>M;
    for(int i=1; i<=M; ++i)
    {
        fin>>x>>y;
        int bin=binary_search(v+1, v+N+1, y);
        int up=upper_bound(v+1, v+N+1, y)-v-1;
        int low=lower_bound(v+1, v+N+1, y)-v;
        if(x==0)
        {
            if(bin) fout<<up<<"\n";
            else fout<<"-1\n";
        }
        else if(x==1)
            fout<<up<<"\n";
        else if(x==2)
            fout<<low<<"\n";
    }
    return 0;

}