#include <bits/stdc++.h>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100000];
int main()
{
    int N,M,p;
    f>>N;
    for(int i=1;i<=N;i++)
        f>>v[i];
    f>>M;
    while(M--)
    {
        int intrebare,X;
        f>>intrebare>>X;
        if(intrebare==0)
        {
            int st,dr,m;
            p=0;
            st=1,dr=N;
            do
            {
                m=(st+dr)/2;
                if(v[m]<X)
                    st=m+1;
                else
                    if(v[m]>X)
                {
                    dr=m-1;

                }
                else if(v[m]==X)
                {
                    if(m>p)
                        p=m;
                    st=m+1;
                }

            }while(st<=dr);
        }
        else if(intrebare==1)
        {
            int st,dr,m;
            p=0;
            st=1,dr=N;
            do
            {
                m=(st+dr)/2;
                if(v[m]<=X)
                {
                    if(m>p)
                        p=m;
                    st=m+1;
                }
                else
                    dr=m-1;

            }while(st<=dr);
        }
        else
        {
            int st,dr,m;
            p=100002,st=1,dr=N;
            do
            {
                m=(st+dr)/2;
                if(v[m]<X)
                    st=m+1;
                else if(v[m]>=X)
                {
                    if(m<p)
                        p=m;
                    dr=m-1;
                }
            }while(st<=dr);
        }
        g<<p<<'\n';
    }

}