#include <iostream>
#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int v[100005];
int n;

void citire()
{
    int i;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
    }
}


int cautbinara1(int x)
{
    int sol = -1, l = 1, r = n;
    while(l<=r)
    {
        int mid = (l+r)/2;

        if(v[mid]>x)
        {
            r=mid-1;
        }
        if(v[mid]<=x)
        {
            l=mid+1;
            sol = mid;
        }
    }
    if(v[sol]!=x)
        return -1;
    return sol;
}

int cautbinara2(int x)
{
    int sol = 0, l = 1, r = n;
    while(l<=r)
    {
        int mid = (l+r)/2;

        if(v[mid]>x)
        {
            r=mid-1;
        }
        if(v[mid]<=x)
        {
            l=mid+1;
            sol = mid;
        }
    }
    return sol;
}

int cautbinara3(int x)
{
    int sol = 0, l = 1, r = n;
    while(l<=r)
    {
        int mid = (l+r)/2;

        if(v[mid]>=x)
        {
            r=mid-1;
            sol=mid;
        }
        if(v[mid]<x)
        {
            l=mid+1;
        }
    }
    return sol;
}


int main()
{
    citire();
    int M,intr,x;
    f>>M;
    for(int i=1;i<=M;i++)
    {
        f>>intr>>x;
        if(intr==0)
            g<<cautbinara1(x)<<endl;
        if(intr==1)
            g<<cautbinara2(x)<<endl;
        if(intr==2)
            g<<cautbinara3(x)<<endl;

    }

}