#include <fstream>
#define NMAX 100005
#define inf 1<<31
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int V[NMAX],N,M;

int cautbin0(int x,int s,int d)
{ int m;
    while (s<d)
            {m=s+(d-s)/2;
            if (V[m]>x) s=m-1;
                else d=m+1;
            if (x==V[m]) return m;
            }
    return 0;
}
int cautbin12(int x,int s,int d)
{ int m;
    while (s<d)
            {m=s+(d-s)/2;
            if (V[m]<x) s=m-1;
                else d=m+1;
            if (x==V[m]) return m;
            }
return m;
}




int main()
{
    int m,op,i,x;
    f>>N;
    for (i=1;i<=N;i++)
        f>>V[i];
    V[N+1]=inf;
    f>>M;
    for (i=1;i<=M;i++)
        {
        f>>op>>x;
        switch (op)
            {
            case 0:
            m=cautbin0(x,1,N);
            while (V[m]==x) m++;
            g<<m-1<<"\n";
            break;
            case 1:
            m=cautbin12(x,1,N);
            while (V[m]<=x) m++;
            g<<m-1<<"\n";
            break;
            case 2:
            m=cautbin12(x,1,N);
            while (V[m]>=x) m--;
            g<<m+1<<"\n";
            break;
            }
        }
    return 0;
}