#include <bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N,M;
vector<int> v;
void citire()
{
    f>>N;
    for(int i=1;i<=N;++i)
    {
        int x;
        f>>x;
        v.push_back(x);
    }
    f>>M;
}
int main()
{
    citire();
    for(int i=1;i<=M;++i)
    {
        int x,y;
        f>>x>>y;
        if(x==0)
        {
            if(binary_search(v.begin(),v.end(),y)==true)
                g<<(upper_bound(v.begin(),v.end(),y)-v.begin())<<'\n';
            else
                g<<-1<<'\n';
        }
        else if(x==1)
        {
            if(binary_search(v.begin(),v.end(),y)==true)
                g<<(upper_bound(v.begin(),v.end(),y)-v.begin())<<'\n';
            else
                g<<(lower_bound(v.begin(),v.end(),y)-v.begin())<<'\n';
        }
        else if(x==2)
        {
            if(binary_search(v.begin(),v.end(),y)==true)
                g<<(lower_bound(v.begin(),v.end(),y)-v.begin())+1<<'\n';
            else
                g<<(upper_bound(v.begin(),v.end(),y)-v.begin())+1<<'\n';
        }
    }
    return 0;
}