#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[10010];
int cautare1(int p,int u,int key)
{int m;
while (p<=u){
        m=(p+u)/2;
        if (v[m]<=key)
            p=m+1;
        else
            u=m-1;
    }
    m=(p+u)/2;

    if (v[m]>key)m--;
    if (v[m]==key)
        return m;
    return -1;
}
 int cautare2(int p,int u,int key)
{ int m, n = u;

    while(p<u){
        m=(p+u)/2;
        if(v[m]<=key)
            p=m+1;
        else
            u=m;
    }

    m=(p+u)/2;
    if (v[m]>key)
       --m;
    return m;
}
 int cautare3(int p,int u,int key) {
    int m;

    while(p<u){
        m=(p+u)/2;
        if (v[m]<key)
            p=m+1;
        else
            u=m;
    }

    m=(p+u)/2;
    if (v[m]<key)
       ++m;
    return m;
}
int main()
{int i,n,tip,val,m;
f>>n;for(i=1;i<=n;i++)f>>v[i];
    f>>m;
    while (m --){
          f>>tip>>val;
          if (tip == 0)
           g<<cautare1(1,n, val)<<'\n';
          if (tip == 1)
            g<<cautare2(1, n, val)<<'\n';;
          if (tip == 2)
            g<<cautare3(1, n, val)<<'\n';;
    }
    return 0;
}