#include <iostream>
#include <stdio.h>

using namespace std;

FILE *f=fopen("cautbin.in","r");
FILE *g=fopen("cautbin.out","w");


int a[100000],nr,mx,n,i,z,c;

int cautbin0(int l, int r)
{
    int m;
    while(l+1<r)
    {
        m=(l+r)/2;
        if(nr<a[m])r=m; else l=m;

    }
    if(a[m]==nr) return m;
     return -1;
}

int cautbin1(int l, int r)
{
    int m;
    while(l+1<r)
    {
        m=(l+r)/2;
        if(nr>=a[m])l=m; else r=m;

    }
    return m;
}

int cautbin2(int l, int r)
{
    int m;
    while(l+1<r)
    {
        m=(l+r)/2;
        if(nr<=a[m])r=m; else l=m;
    }
    return m;
}




int main()
{
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(f,"%d",&a[i]);
    fscanf(f,"%d",&z);
    for(i=1;i<=z;i++)
    {
        fscanf(f,"%d %d",&c,&nr);

        switch(c)
        {
            case 0:{mx=cautbin0(1,n);break;}
            case 1:{mx=cautbin1(1,n);break;}
            case 2:{mx=cautbin2(1,n);break;}
        }
        fprintf(g,"%d\n",mx);
    }

    fclose(g);
    return 0;
}