#include <iostream>
#include <fstream>
#define Nmax 100000
using namespace std;
int a[Nmax];
int Bsearch1(int s , int d, int x,int p)
{    if(s<=d)
    {
        int mij=(s+d)/2;
        if(x==a[mij])
            return Bsearch1(mij+1,d,x,mij);
        else
        {
            if(x>a[mij])
                return Bsearch1(mij+1,d,x,p);
            else
                return Bsearch1(s,mij-1,x,p);
        }
    }
    else
    {
        if(p>-1)
            return p;
        else
            return -1;
    }
}
int Bsearch2(int s , int d, int x,int p)
{    if(s<=d)
    {
        int mij=(s+d)/2;
        if(x>=a[mij])
            return Bsearch2(mij+1,d,x,mij);
        else
            return Bsearch2(s,mij-1,x,p);
    }
    else
    {
        if(p>-1)
            return p;
        else
            return -1;
    }
}
int Bsearch3(int s , int d, int x,int p)
{    if(s<=d)
    {
        int mij=(s+d)/2;
        if(x<=a[mij])
            return Bsearch3(s,mij-1,x,mij);
        else
            return Bsearch3(mij+1,d,x,p);
    }
    else
    {
        if(p>-1)
            return p;
        else
            return -1;
    }
}
int Bsearch3(int s , int d, int x);
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int n,x,y,m;
    f>>n;
    for(int i=1;i<=n;i++)
        f>>a[i];
    f>>m;
    for(int i=1;i<=m;i++)
    {
        f >>x>>y;
        if(x==0)
            g<<Bsearch1(1,n,y,-2)<<"\n";
        if(x==1)
            g<<Bsearch2(1,n,y,-2)<<"\n";
        if(x==2)
            g<<Bsearch3(1,n,y,-2)<<"\n";
    }

    return 0;
}