#include <stdio.h>

int v[100010];

int cb0 (int n, int y)
{
    int start=0,stop=n-1,mid=n/2,max=-1,m=0;
    while (1)
    {
        if (v[mid]==y && mid>max)
            max=mid;
        if (v[mid]<=y)
            start=mid;
        else
            stop=mid;
        if (mid==0 || mid==n-1 || max==n-1) break;
        m=mid;
        mid=(start+stop)/2+(start+stop)%2;
        if (mid==m) ++mid;
    }
    return max;
}

int cb1 (int n, int y)
{
    int start=0,stop=n-1,mid=n/2,max=0,m=0;
    while (1)
    {
        if (v[mid]<=y && mid>max)
            max=mid;
        if (v[mid]<=y)
            start=mid;
        else
            stop=mid;
        if (mid==0 || mid==n-1 || max==n-1) break;
        m=mid;
        mid=(start+stop)/2+(start+stop)%2;
        if (m==mid) ++mid;
    }
    return max;
}

int cb2 (int n, int y)
{
    int start=0,stop=n-1,mid=n/2,min=100010,m=0;
    while (1)
    {
        if (v[mid]>=y && mid<min)
            min=mid;
        if (y<=v[mid])
            stop=mid;
        else
            start=mid;
        if (mid==0 || mid==n-1 || min==0) break;
        m=mid;
        mid=(start+stop)/2+(start+stop)%2;
        if (mid==m) --mid;
    }
    return min;
}

int main()
{
    int n=0,x=0,y=0,i=0,m=0;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for (i=0; i<n; ++i)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for (i=0; i<m; ++i)
    {
        scanf("%d%d",&x,&y);
        if (x==0)
            printf("%d\n",cb0(n,y)+1);
        else if (x==1)
            printf("%d\n",cb1(n,y)+1);
        else
            printf("%d\n",cb2(n,y)+1);
    }
    return 0;
}