#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100001];
int n;
int m;
int op;
int val;
int MAX_STEP=1;
int bSearch1(int x)
{   
    int pos=1;
    for(int i=MAX_STEP;i>0;i/=2)
    {
        if(pos+i<n&&v[pos+i]<=x)
        {
            pos=pos+i;
        }
    }
    return pos;
}
int bSearch0(int x)
{   
    int pos=bSearch1(x);
    if(v[pos]==x)
        return pos;
    else 
        return -1;
}
int bSearch2(int x)
{   
    int pos=n;
    for(int i=MAX_STEP;i>0;i/=2)
    {
        if(v[pos-i]>=x&&pos-i>=1)
        {
            pos=pos-i;
        }
    }
    return pos;
}
int main() {
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
    }
    while(MAX_STEP<n)
    {
        MAX_STEP=MAX_STEP*2;
    }
    f>>m;
    for(int i=0;i<m;i++)
    {
        cin>>op;
        cin>>val;
        if(op==0)
            g<<bSearch0(val)<<'\n';
        else if(op==1)
            g<<bSearch1(val)<<'\n';
        else
            g<<bSearch2(val)<<'\n';
    }
}