#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int m,n,x,v[100005],a;

int a0(int e1, int e2, int x)
{
    int mij;
   while(e1<=e2)
   {
       mij=(e1+e2)/2;
       if(v[mij]<=x) e1=mij+1;
       else e2=mij-1;
   }
   mij=(e1+e2)/2;
   if(v[mij]>x) mij--;
   if(v[mij]==x) return mij;
   return -1;
}

int a1(int b1, int b2, int x)
{
    int mij;
    while(b1<b2)
    {
        mij=(b1+b2)/2;
        if(v[mij]<=x) b1=mij+1;
        else b2=mij;
    }
    mij=(b1+b2)/2;
    if(v[mij]>x) mij--;
    return mij;
}

int a2(int c1, int c2, int x)
{
    int mij;
    while(c1<c2)
    {
        mij=(c1+c2)/2;
        if(v[mij]<x) c1=mij+1;
        else c2=mij;
    }
    mij=(c1+c2)/2;
    if(v[mij]<x) mij++;
    return mij;
}

int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
        fin >> v[i];
    fin >> m;
    for(int i=1;i<=m;i++)
    {
        fin >> a >> x;
       if(a==0)  fout << a0(1,n,x) << '\n';
        if(a==1) fout << a1(1,n,x) << '\n';
       if(a==2) fout << a2(1,n,x) << '\n';

    }
    return 0;
}