#include<bits/stdc++.h>

using namespace std;

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

int n,m,a[100005];
int main()
{

    fin >> n;
    for(int i=1;i<=n;i++)
        fin >> a[i];
    fin >> m;

    while(m--)
    {
        int t,x,l=1,r=n,q=-1;
        fin >> t >> x;
        if(t<=1)
            while(l<=r)
            {
                int m=l+(r-l)/2;
                if(a[m]<=x)
                {
                    l=m+1;
                    if(t or a[m]==x)
                        q=max(q,m);
                }
                else
                    r=m-1;
            }
        else
        {
            q=n;
            while(l<=r)
            {
                int m=l+(r-l)/2;
                if(a[m]<x)
                    l=m+1;
                else
                    r=m-1, q=min(q,m);
            }
        }
        fout << q << "\n";
    }

    return 0;

}