#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100005];
int i,n,m;
int x,y;
int val;
void Citire()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;

}

int Cautare(int x,int n,int y)
{
    if(x==0)
    {
    bool ok=false;
    int poz=-1;
    int Left=1;
    int Right=n;
    while(Left<=Right)
    {

        int Mid=(Left+Right)/2;
       //fout<<y;
        if(y==v[Mid])
        {
            poz=Mid;
            ok=true;
        }
        if(ok)
        {
            ok=false;
            Left=Mid+1;
        }
        else
        {
            if(y<v[Mid])
            {
                Right=Mid-1;
            }
            else
            {
                Left=Mid+1;
            }
        }

    }
    return poz;
    }
    if(x==1)
    {
    bool ok=false;
    int poz=-1;
    int Left=1;
    int Right=n;
    while(Left<=Right)
    {

        int Mid=(Left+Right)/2;
       //fout<<y;
        if(y>=v[Mid])
        {
            poz=Mid;
            ok=true;
        }
        if(ok)
        {
            ok=false;
            Left=Mid+1;
        }
        else
        {
            if(y<v[Mid])
            {
                Right=Mid-1;
            }
            else
            {
                Left=Mid+1;
            }
        }

    }
    return poz;
    }
    if(x==2)
    {
        bool ok=false;
    int poz=-1;
    int Left=1;
    int Right=n;
    while(Left<=Right)
    {

        int Mid=(Left+Right)/2;
       //fout<<y;
        if(y<=v[Mid])
        {
            poz=Mid;
            ok=true;
        }
        if(ok)
        {
            ok=false;
            Right=Mid-1;
        }
        else
        {
            if(y<v[Mid])
            {
                Right=Mid-1;
            }
            else
            {
                Left=Mid+1;
            }
        }

    }
    return poz;
    }
}

int  main()
{
    Citire();
    for(i=1;i<=m;i++)
    {
        int s=0;
        fin>>x>>y;
       // fout<<y;
        fout<<Cautare(x,n,y)<<"\n";

    }
    return 0;
}