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

int main()
{
    int n,v[100001],m,a,b;
    int lt,rt,md;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    bool ok;
    f>>n;
    for(int i=1; i<=n; ++i)
    {
        f>>v[i];
    }
    f>>m;
    for(int j=1; j<=m; ++j)
    {
        f>>a>>b;
        rt=n+1;
        lt=0;
        md=0;
        ok=false;
        if(a==0)
        {
            while(rt-lt!=1)
            {
                md=lt+(rt-lt)/2;
                if(v[md]<=b) lt=md;
                else rt=md;
                if(v[md]==b) ok=true;
            }
            md=lt+(rt-lt)/2;
            if(ok) g<<md<<"\n";
            else g<<"-1"<<"\n";
        }
        if(a==1)
        {
            while(rt-lt!=1)
            {
                md=lt+(rt-lt)/2;
                if(v[md]<=b) lt=md;
                else rt=md;
            }
            md=lt+(rt-lt)/2;
            g<<md<<"\n";
        }
        if(a==2)
        {
            while(rt-lt!=1)
            {
                md=lt+(rt-lt)/2;
                if(v[md]>=b) rt=md;
                else lt=md;
            }
            g<<rt<<"\n";
        }
    }
}