#include <bits/stdc++.h>

using namespace std;

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

const int nmax=1e5+10;
int n,m,a[nmax],p=1;

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

int binarySearch1(int x)
{
    int i,l;
    for(i=0,l=p;l>0;l>>=1)
        if(i+l<=n && a[i+l]<=x)
            i+=l;
    if(a[i]==x)
        return i;
    else
        return -1;
}

int binarySearch2(int x)
{
    int i,l;
    for(i=0,l=p;l>0;l>>=1)
        if(i+l<=n && a[i+l]<=x)
            i+=l;
    return i;
}

int binarySearch3(int x)
{
    int i,l;
    for(i=n,l=p;l>0;l>>=1)
        if(i-l>=1 && a[i-l]>=x)
            i-=l;
    return i;
}

void solve()
{
    fin>>m;
    for(int i=0;i<m;i++)
    {
        int q,x;
        fin>>q>>x;
        switch(q)
        {
        case 0:
            fout<<binarySearch1(x)<<"\n";
            break;
        case 1:
            fout<<binarySearch2(x)<<"\n";
            break;
        case 2:
            fout<<binarySearch3(x)<<"\n";
            break;
        }
    }
}

int main()
{
    read();
    solve();
    return 0;
}