#include <iostream>
#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100005],x,i,t,s,d,a,n;
int bs0(int s,int d)
{
    int m;
    while(s<=d)
    {
        m=s+(d-s)/2;
        if(v[m]==x) s = m+1;
        else
            if(v[m]>x) d = m - 1;
            else s = m + 1;
    }
    m=s+(d-s)/2;
    if(v[m]==x) return m;
    else{ m--;
        if(v[m]==x) return m;
        else return -1;}
}
int bs1 (int s,int d)
{
    int m;
    while(s<d)
    {
        m=s+(d-s)/2;
        if(v[m]<=x) s = m + 1;
        else d = m - 1;
    }
    m=s+(d-s)/2;
     if(v[m]<=x) return m;
     else {m--;if(v[m]<=x)return m;}
}
int bs2 (int a,int b)
{
    int m;
    while(s<d)
    {
        m=s+(d-s)/2;
        if(v[m]>=x) d = m ;
        else s = m + 1;
    }
    m=s+(d-s)/2;m++;
    if(v[m]>=x) return m;
    else {m++;if(v[m]>=x)return m;}
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>a>>x;
        if(a==0)
            g<<bs0(1,n)<<"\n";
        else if(a==1) g<<bs1(1,n)<<"\n";
             else g<<bs2(1,n)<<"\n";
    }
    return 0;
}