#include <iostream>
#include <fstream>

using namespace std;

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

int *v;
unsigned int n;

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

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

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

int main()
{
   unsigned int m;
    in>>n;
    v = new int[n+2];
    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;
}