#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,i,v[100003],nrq;
int caut0(int x)
{
    int in=1,sf=n,mij;
    while(in<sf)
    {
        mij=(in+sf)/2;
        if(v[mij]==x && v[mij+1]>x)return mij;
        else if(v[mij]<=x)in=mij+1;
        else if(v[mij]>x)sf=mij-1;
    }
    if(v[mij]!=x && v[mij+1]!=x)return -1;
}
int caut1(int x)
{
    int in=1,sf=n,mij;
    while(in<sf)
    {
        mij=(in+sf)/2;
        if(v[mij]<=x && v[mij+1]>x)return mij;
        else if(v[mij]<=x)in=mij+1;
        else if(v[mij]>x)sf=mij-1;
    }
}
int caut2(int x)
{
    int in=1,sf=n,mij;
    while(in<sf)
    {
        mij=(in+sf)/2;
        if(v[mij]>=x && v[mij-1]<x)return mij;
        else if(v[mij]<x)in=mij+1;
        else if(v[mij]>=x)sf=mij-1;
    }
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>nrq;
    for(i=1;i<=nrq;i++)
    {
        short type;int val;
        f>>type>>val;
        if(type==0)
            g<<caut0(val);
        else if(type==1)
            g<<caut1(val);
        else g<<caut2(val);
        g<<'\n';
    }
}