#include <cstdio>

using namespace std;
const char InFile[]="cautbin.in";
const char OutFile[]="cautbin.out";
const int DIMN=100010;

int n,m,v[DIMN],y;

int binarySearch0(int a,int b,int x)
{
    int mid=(a+b)/2;
    if(a<=b)
    {
    if(x<v[mid])
        return binarySearch0(a,mid-1,x);
    else if(x==v[mid])
         {
             y=mid;
             return binarySearch0(mid+1,b,x);
         }
    else return binarySearch0(mid+1,b,x);
    }
    return y;
}

int binarySearch1(int a,int b,int x)
{
       int mid=(a+b)/2;
    if(a<=b)
    {
    if(x>=v[mid])
    {
        y=mid;
        return binarySearch1(mid+1,b,x);
    }
    else return binarySearch1(a,mid-1,x);
    }
    return y;

}

int binarySearch2(int a,int b,int x)
{
    int mid=(a+b)/2;
    if(a<=b)
    {
    if(x<=v[mid])
    {
        y=mid;
        return binarySearch2(a,mid-1,x);
    }
    else return binarySearch2(mid+1,b,x);
    }
    return y;
}

int main()
{
    int a,b;
    freopen(InFile,"r",stdin);
    freopen(OutFile,"w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&a,&b);
        y=-1;
        if(a==0)
        {
            printf("%d\n",binarySearch0(1,n,b));
        }
        if(a==1)
        {
            printf("%d\n",binarySearch1(1,n,b));
        }
        if(a==2)
        {
            printf("%d\n",binarySearch2(1,n,b));
        }
    }

    return 0;
}