#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define n 100010

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

int val,v[n],problema;
int rez1(int s, int d, int val)
{
    int mijl;
    mijl=(s+d)/2;
    if(val>=v[mijl])
    {
        s=mijl+1;
        return rez1(s,d,val);
    }
    d=mijl-1;
    mijl=(s+d)/2;
    if(v[mijl] > val)
        --mijl;
    if(v[mijl]==val)
        return mijl;
    return -1;

}

int rez2(int s,int d,int val)
{
    int mijl;
    mijl=(s+d)/2;
    if(val>=v[mijl])
    {
        s=mijl+1;
        return rez1(s,d,val);
    }
    d=mijl;
    mijl=(s+d)/2;
    if(v[mijl] > val)
        --mijl;
    return mijl;

}

int rez3(int s, int d, int val)
{
    int mijl;

    mijl=(s+d)/2;
    if(val>v[mijl])
    {
        s=mijl+1;
        return rez1(s,d,val);
    }
    d=mijl;
    mijl=(s+d)/2;
    if(v[mijl] > val)
        ++mijl;
    return mijl;
}

int main()
{
    int i,N,M,val,problema;
    f>>N;
    for(i=1; i<=N; i++)
        f>>v[i];
    f>>M;
    for(i=1; i<=M; i++)
    {
        f>>problema>>val;
        if(problema==0)
            g<<rez1(1,N,val)<<endl;
        else if(problema==1)
            g<<rez2(1,N,val)<<endl;
        else if(problema==2)
            g<<rez3(1,N,val)<<endl;
    }




    return 0;
}