#include <bits/stdc++.h>
using namespace std;
int n,v[100005];
int cautbin0(int inc,int sf,int x)
{
    if(inc>sf)
        return -1;
    int m=(inc+sf)/2;
    if(v[m]<x)
        return cautbin0(m+1,sf,x);
    if(v[m]>x)
        return cautbin0(inc,m-1,x);
    if(v[m]==x&&v[m+1]==x)
        return cautbin0(m+1,sf,x);
    return m;
}
int cautbin1(int inc,int sf,int x)
{
    if(inc>sf)
        return -1;
    int m=(inc+sf)/2;
    if(v[m]<=x&&v[m+1]<=x&&m!=n)
        return cautbin1(m+1,sf,x);
    if(v[m]>x)
        return cautbin1(inc,m-1,x);
    return m;
}
int cautbin2(int inc,int sf,int x)
{
    if(inc>sf)
        return -1;
    int m=(inc+sf)/2;
    if(v[m]<x)
        return cautbin2(m+1,sf,x);
    if(v[m]>=x&&v[m-1]>=x&&m!=1)
        return cautbin2(inc,m-1,x);
    return m;
}
int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    int i,t,x,m;
    v[n+1]=(1<<31)-1;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>t>>x;
        if(t==0)
            out<<cautbin0(1,n,x)<<'\n';
        if(t==1)
            out<<cautbin1(1,n,x)<<'\n';
        if(t==2)
            out<<cautbin2(1,n,x)<<'\n';
    }
    return 0;
}