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