#include <stdio.h>
#include <stdlib.h>
int v[100000];
int tip0(int p,int u,int val)
{
    int m;
    while(p<=u)
    {
        m=(u+p)/2;
        if(v[m]<=val)
        {
            p=m+1;
        }else{
            u=m-1;
        }
    }

    if(v[m]>val)return m-1;
    if(v[m]==val)return m;
    return -1;
}
int tip1(int p,int u,int val)
{
    int m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(v[m]<=val)
        {
            p=m+1;
        }else{
            u=m-1;
        }
    }
    if(v[m]>val)return m-1;
    if(v[m]==val)return m;
}
int tip2(int p,int u,int val)
{
    int m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(v[m]>=val)
        {
            u=m-1;
        }else{
            p=m+1;
        }
    }
    if(v[m]>val)return m-1;
    if(v[m]==val)return m;
}
int main()
{
    FILE *in,*out;
    in=fopen("cautbin.in","r");
    out=fopen("cautbin.out","w");
    int i,n,k,tip,val;
    fscanf(in,"%d\n",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d",&v[i]);
    }
    fscanf(in,"%d",&k);
    for(i=1;i<=k;i++)
    {
        fscanf(in,"%d %d\n",&tip,&val);
        if(tip==0)
        {
            fprintf(out,"%d\n",tip0(1,n,val));
        }
        if(tip==1)
        {
            fprintf(out,"%d\n",tip1(1,n,val));
        }
        if(tip==1)
        {
            fprintf(out,"%d\n",tip2(1,n,val));
        }
    }
    return 0;
}