#include <fstream>
#define DIM 100010
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n, a[DIM],m,i,o,y;

int sb0(int x, int r, int l)
{
    m=r+(l-r)/2;
    if(r>l)
        return -1;
    if(a[m]==x&&(a[m+1]>x||m+1>n))
        return m;
    else
        {
            if(a[m]>x)
                return sb0(x,r,m-1);
            else
                return sb0(x,m+1,l);
        }
}

int sb1(int x, int r, int l)
{
    m=r+(l-r)/2;
    if(r>l)
        return -1;
    if(a[m]<=x&&(a[m+1]>x||m+1>n))
        return m;
    else
        {
            if(a[m]>x)
                return sb1(x,r,m-1);
            else
                return sb1(x,m+1,l);
        }

}

int sb2(int x, int r, int l)
{
    m=r+(l-r)/2;
    if(r>l)
        return -1;
    if(a[m]>=x&&(a[m-1]<x||m+1>n))
        return m;
    else
        {
            if(a[m]>x)
                return sb2(x,r,m-1);
            else
                return sb2(x,m+1,l);
        }

}

int main()
{
    f>>n;
    for(i=1; i<=n; i++)
        f>>a[i];
    f>>m;
    for(;m;m--)
        {
            f>>o>>y;
            if(o==0)
                g<<sb0(y,1,n)<<"\n";
            if(o==1)
                g<<sb1(y,1,n)<<"\n";
            if(o==2)
                g<<sb2(y,1,n)<<"\n";
        }
    return 0;
}