#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int i,n,m,k,x,t[100011];
int c0(int x, int i, int j)
{
    int m;
    if(t[m]==x) return m;
        else if (i>=j) return -1;
                 else
                 {
                     m=(j+i)/2;
                     return c0(x,i,m-1);
                     return c0(x,m+1,j);
                 }
}
int c1(int x, int i, int j)
{
    if (i>j) return j;
    int m=(j+i)/2;
    if (t[m]<=x) return c1(x,m+1,j);
    return c1(x,i,m-1);

}
int c2(int x, int i, int j)
{
    if (i>j) return i;
    int m=i+(j-i)/2;
    if (t[m]>=x) return c2(x,i,m-1);
    return c2(x,m+1,j);
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++) fin>>t[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>k>>x;
        if (k==0) fout<<c1(x,1,n)<<'\n';
            else if (k==1) fout<<c1(x,1,n)<<'\n';
                     else fout<<c2(x,1,n)<<'\n';
    }
    return 0;
}