#include <iostream>
#include <fstream>

using namespace std;

fstream in("cautbin.in",ios::in);
fstream out("cautbin.out",ios::out);

int *v;

int binar_0(int *v,unsigned int x,unsigned int y,int val)
{
    if(x<=y)
    {
        unsigned int m = (x+y)/2;
        if((v[m]==val) && (v[m+1]!=val))
            return m;
        else
        {
            if(v[m]<=val)
                return binar_0(v,m+1,y,val);
            else
                return binar_0(v,x,m-1,val);
        }
    }
    return -1;
}

int binar_1(int *v,unsigned int x,unsigned int y,int val)
{
    if(x<=y)
    {
        unsigned int m = (x+y)/2;
        if((v[m]<=val) && (v[m+1]!=v[m]))
            return m;
        else
        {
            if(v[m]<=val)
                return binar_1(v,m+1,y,val);
            else
                return binar_1(v,x,m-1,val);
        }
    }
    return -1;
}

int binar_2(int *v,unsigned int x,unsigned int y,int val)
{
    if(x<=y)
    {
        unsigned int m = (x+y)/2;
        if((v[m]>=val) && (v[m]!=v[m-1]))
            return m;
        else
        {
            if(v[m]>=val)
                return binar_2(v,x,m-1,val);
            else
                return binar_2(v,m+1,y,val);
        }
    }
    return -1;
}

int main()
{
    unsigned int n,m;
    in>>n;
    v = new int[n+1];
    for(unsigned int i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    int x,y;
    for(unsigned int i=1;i<=m;i++)
    {
        in>>x>>y;
       if(x==0)
        out<<binar_0(v,1,n,y)<<'\n';
        else
            if(x==1)
            out<<binar_1(v,1,n,y)<<'\n';
        else
            out<<binar_2(v,1,n,y)<<'\n';
    }
    delete[] v;
    return 0;
}