#include <iostream>
#include <fstream>
using namespace std;

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


int n,v[100000];

int cautbin0(int x)
{
int step;
    for(step=1; step<=n; step=step*2)
    {}
    step=step/2;
    int sol=0;
    for(; step>=1; step=step/2)
    {
        if(sol+step<=n && v[sol+step]<=x)
        {
            sol=sol+step;
        }
    }
    if(v[sol]==x)
        return sol;
    return -1;
}

int cautbin2(int x)
{
    int step;
    for(step=1; step<=n; step=step*2)
    {}
    step=step/2;

    int sol;
    for(sol=n; step>=1; step=step/2)
    {
        if(sol-step>0 && v[sol-step]>=x)
        {
            sol=sol-step;
        }
    }
    return sol;
}

int cautbin1(int x)
{
    int step;
    for(step=1; step<=n; step=step*2)
    {}
    step=step/2;
    int sol=0;
    for(; step>=1; step=step/2)
    {
        if(sol+step<=n && v[sol+step]<=x)
        {
            sol=sol+step;
        }
    }
    return sol;
}


int main()
{
    int x;
    int opt,m;
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>v[i];
    }
    in>>m;
    for(int i=1; i<=m; i++)
    {
        in>>opt>>x;
        if(opt==0)
            out<<cautbin0(x)<<'\n';
        else if(opt==1)
            out<<cautbin1(x)<<'\n';
        else
            out<<cautbin2(x)<<'\n';

    }

}