#include <bits/stdc++.h>

#define N 100000

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int a[N+5], n, k;

int cautbin0(int x)
{
    int st=1, dr=n, mij, poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]==x) st=mij+1, poz=mij;
        else if(a[mij]>x) dr=mij-1;
            else st=mij+1;
    }
    return poz;
}

int cautbin1(int x)
{
    int st=1, dr=n, mij, poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x) st=mij+1, poz=mij;
        else dr=mij-1;
    }
    return poz;
}

int cautbin2(int x)
{
    int st=1, dr=n, mij, poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]>=x) dr=mij-1, poz=mij;
        else st=mij+1;
    }
    return poz;
}

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

void cerinta()
{
    int task, x, i;
    fin >> k;
    for(i=1;i<=k;++i)
    {
        fin >> task >> x;
        if(task==0) fout << cautbin0(x);
        if(task==1) fout << cautbin1(x);
        if(task==2) fout << cautbin2(x);
        fout << "\n";
    }
    fin.close();
    fout.close();
}

int main()
{
    citire();
    cerinta();
    return 0;
}