#include<iostream>
#include<stdio.h>
using namespace std;
#define maxN 100005

int tip0(int x, int v[], int n)
{
    int gasit=0; int poz=-2;
    int st=0, dr=n;
    int m;
    while(!gasit && st<=dr)
    {
        m=st+(dr-st)/2;
        if(v[m]==x)
        {
            poz=m;;
            gasit=1;
        }
        else if(x<v[m])
                dr=m-1;
        else
                st=m+1;
    }

    for(int i=poz;v[i]==x;++i)
     poz=i;
return poz;


}

int tip1(int x, int v[], int n)
{
    int gasit=0; int poz=-1;
    int st=0, dr=n;
    int m;
    while(!gasit && st<=dr)
    {
        m=st+(dr-st)/2;
        if(v[m]<=x)
        {
            poz=m;;
            gasit=1;
        }
        else if(x<v[m])
                dr=m-1;
        else
                st=m+1;
    }

    for(int i=poz;v[i]<=x;++i)
        poz=i;

    return poz;

}
int tip2(int x, int v[],int n)
{
int gasit=0; int poz=-1;
    int st=0, dr=n;
    while(!gasit && st<=dr)
    {
        int m=st+(dr-st)/2;
        if(v[m]>=x)
        {
            poz=m;
            gasit=1;
        }
        else if(x<v[m])
                dr=m-1;
        else
                st=m+1;
    }

    for(int i=poz;v[i]>=x;--i)
        poz=i;

    return poz;

}

int main()
{
    int m,n,g; int v[maxN];
    freopen("cautbin.in", "r", stdin);

    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &v[i]);
    }
    scanf("%d", &m);

    freopen("cautbin.out", "w", stdout);

    int t;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d", &t, &g);
        switch(t)
        {
            case 0: printf("%d\n",tip0(g,v,n)); break;
            case 1: printf("%d\n",tip1(g,v,n)); break;
            case 2: printf("%d\n",tip2(g,v,n)); break;
        }
    }


    return 0;
}