#define Dudica "Dudescu Alexandru"
#include <cstdio>
#define nmax 100005
using namespace std;
FILE *f1=fopen("cautbin.in","r"),*f2=fopen("cautbin.out","w");
int n,m,v[nmax],opt;
int cautaBinar0(int x)
{
    int st,dr,mij;
    st=1;dr=n;
    while(dr-st>1)
    {
        mij=st+(dr-st)/2;
        if(v[mij]<=x)
        st=mij;
        else
        dr=mij;
    }
        if(v[st]<x)st++;
        if(v[st]==x)return st;
        return -1;
}
int cautaBinar1(int x)
{
    int st,dr,mij;
    st=1;dr=n;
    while(dr-st>1)
    {
        mij=st+(dr-st)/2;
        if(v[mij]<x)
        st=mij;
        else
        dr=mij;
    }
        if(v[dr]>x)dr--;
        return dr;
}
int cautaBinar2(int x)
{
    int st,dr,mij;
    st=1;dr=n;
    while(dr-st>1)
    {
        mij=st+(dr-st)/2;
        if(v[mij]<x)
        st=mij;
        else
        dr=mij;
    }
    if (v[st]<x) st++;
    return st;
}
int main()
{
    int i,key;
    fscanf(f1,"%d",&n);
    for(i=1;i<=n;i++)fscanf(f1,"%d ",&v[i]);
    fscanf(f1,"%d",&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f1,"%d %d",&opt,&key);
        if(opt==0)fprintf(f2,"%d\n",cautaBinar0(key));
        else if(opt==1) fprintf(f2,"%d\n",cautaBinar1(key));
        else fprintf(f2,"%d\n",cautaBinar2(key));
    }
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.