#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

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

int v[NMAX],n,m;

int cauta0(int st,int dr,int val)
{
    if(st == dr)
    {
        if(v[st] > val)st--;
        return v[st] == val ? st : -1;
    }
    else
    {
        int mid = st + (dr - st)/2;
        if(val < v[mid])return cauta0(st,mid-1,val);
        else if(val >= v[mid])return cauta0(mid+1,dr,val);
    }
}

int cauta1(int st,int dr,int val)
{
    if(st == dr)return v[st] <= val ? st : st-1;
    else
    {
        int mid = st + (dr - st)/2;

        if(v[mid] <= val)cauta1(mid+1,dr,val);
        else if(v[mid] > val) return cauta1(st,mid-1,val);
    }
}

int cauta2(int st,int dr,int val)
{
    if(st == dr)return v[st] >= val ? st : st+1;
    {
        int mid = st + (dr - st)/2;

        if(v[mid] >= val)return cauta2(st,mid,val);
        else return cauta2(mid+1,dr,val);
    }
}

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

    int a,b;
    f >> m;
    for(int i=1;i<=m;++i)
    {
        f >> a >> b;
        if(a == 0)
        g << cauta0(1,n,b) << '\n';
        else
        if(a == 1)
        g << cauta1(1,n,b) << '\n';
        else
        g << cauta2(1,n,b) << '\n';
    }
}

int main()
{
    citire();

    return 0;
}