#include <fstream>
#include <vector>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

vector<int> v;

int n, m;

int binary_0(int x)
{
    int hi=v.size()-1, lo=0, mid;
    while(hi-lo>=0)
    {
        mid=(hi+lo)/2;
        if(v[mid]>x)
            hi=mid-1;
        else
            lo=mid+1;
    }

    if (v[hi]!=x)
        return -1;
    return hi+1;
}
int binary_1(int x)
{
    int hi=v.size()-1, lo=0, mid;
    while(hi-lo>=0)
    {
        mid=(hi+lo)/2;
        if(v[mid]<=x)
            lo=mid+1;
        else
            hi=mid-1;
    }
    if(v[lo]!=x)
        return lo;
    return lo+1;
}
int binary_2(int x)
{
    int hi=v.size()-1, lo=0, mid;
    while(hi-lo>=0)
    {
        mid=(hi+lo)/2;
        if(v[mid]<x)
            lo=mid+1;
        else
            hi=mid-1;
    }
    if(v[lo]>=x)
        return lo+1;
    return hi+1;
}
int main()
{
    pair<int, int> q;
    in>>n;
    int x;
    for(int i=0;i<n;i++)
    {
        in>>x;
        v.push_back(x);
    }
    in>>m;
    for(int i=1;i<=m;i++)
    {
        in>>q.first>>q.second;
        if(q.first==0)
            out<<binary_0(q.second)<<"\n";
        else if(q.first==1)
            out<<binary_1(q.second)<<"\n";
        else
            out<<binary_2(q.second)<<"\n";
    }
    return 0;
}