#include<iostream>
#include<fstream>
using namespace std;

ifstream fin("fin.in");
ofstream fout("fout.out");
#define maxN 100005

int tip0(int x, int v[], int n)
{
    int gasit=0; int poz=-1;
    int st=0, dr=n;
    int m;
    while(!gasit && st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]==x)
        {
            poz=m;;
            gasit=1;
        }
        else if(x<v[m])
                dr=m-1;
        else
                st=m+1;
    }

    for(int i=poz;v[i]==x;++i)
     poz=i;
return poz;


}

int tip1(int x, int v[], int n)
{
    int gasit=0; int poz=-1;
    int st=0, dr=n;
    int m;
    while(!gasit && st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<=x)
        {
            poz=m;;
            gasit=1;
        }
        else if(x<v[m])
                dr=m-1;
        else
                st=m+1;
    }

    for(int i=poz;v[i]<=x;++i)
        poz=i;

    return poz;

}
int tip2(int x, int v[],int n)
{
int gasit=0; int poz=-1;
    int st=0, dr=n;
    while(!gasit && st<=dr)
    {
        int m=(st+dr)/2;
        if(v[m]>=x)
        {
            poz=m;
            gasit=1;
        }
        else if(x<v[m])
                dr=m-1;
        else
                st=m+1;
    }

    for(int i=poz;v[i]>=x;--i)
        poz=i;

    return poz;

}

int main()
{
    int n,m,v[maxN];
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>v[i];


    fin>>m;

    int tip,x;
    for(int i=0;i<m;i++)
        {
            fin>>tip;
            fin>>x;
            if(tip)
            {
                if(tip==1)
                fout<<tip1(x,v,n)<<" ";
                else
                fout<<tip2(x,v,n)<<" ";
            }
            else
                fout<<tip0(x,v,n)<<" ";
      }


    return 0;
}