#include <fstream>
#include <iostream>
#define fin "cautbin.in"
#define fou "cautbin.out"
using namespace std;
long sir[100001];
int n,m;

int cbin0(int st,int dr,long x)
{
    long mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(sir[mid]<=x) st=mid+1;
                   else dr=mid-1;
    }
    mid=(st+dr)/2;
    if(sir[mid]>x) mid--;
    if(sir[mid]==x) return mid;
    return -1;
}


int cbin1(int st,int dr,long x)
{
    long mid;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(sir[mid]<=x) st=mid+1;
                   else dr=mid;
    }
    mid=(st+dr)/2;
    if(sir[mid]>x) mid--;
    return mid;
}

int cbin2(int st,int dr,long x)
{
    long mid;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(sir[mid]<x) st=mid+1;
                   else dr=mid;
    }
    mid=(st+dr)/2;
    if(sir[mid]<x) mid++;
    return mid;
}

int main()
{
    ifstream t1(fin);
    ofstream t2(fou);
    int i,j,mod,val,poz,ok;
    t1>>n;
    for(i=1;i<=n;i++) t1>>sir[i];
    t1>>m;
    for(i=1;i<=m;i++)
    {
        t1>>mod>>val;
        if(mod==0) t2<<cbin0(1,n,val)<<'\n';
        if(mod==1) t2<<cbin1(1,n,val)<<'\n';
        if(mod==2) t2<<cbin2(1,n,val)<<'\n';
    }
    t2.close();
    t2.close();
    return 0;
}