#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int v[100001];
int c[100001];
int f[100001];
int coada[101];
unsigned long long int nr1,nr,n,m;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int cauarebinara0(int k)
{
    int step;
    for(step=1; step<=n; step=step*2) {}
    step=step/2;
    int sol=0;
    for(; step>=1; step=step/2)
        if(step+sol<=n and v[sol+step]<=k)
            sol=step+sol;
    if(v[sol]==k)
        return sol;
    else
        return -1;
}
int cauarebinara1(int k)
{
    int step;
    for(step=1; step<=n; step=step*2) {}
    step=step/2;
    int sol=0;
    for(; step>=1; step=step/2)
        if(step+sol<=n and v[sol+step]<=k)
            sol=step+sol;
    return sol;
}
int cauarebinara2(int k)
{
    int step;
    for(step=1; step<=n; step=step*2) {}
    step=step/2;
    int sol=n;
    for(; step>=1; step=step/2)
        if(sol-step>0 and v[sol-step]>=k)
            sol=sol-step;
    return sol;
}

int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>v[i];
    in>>m;
    int x,y;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y;
        if(x==0)
        out<<cauarebinara0(y)<<'\n';
        if(x==1)
            out<<cauarebinara1(y)<<'\n';
        if(x==2)
            out<<cauarebinara2(y)<<'\n';
    }
}