#include <bits/stdc++.h>

using namespace std;

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

int v[100001];

int cautare0(int s, int d, int k)
{
    int m;
    while(s<d)
    {
        m=(s+d)/2;
        if(v[m]<=k)
            s=m+1;
        else
            d=m-1;
    }
    m=(s+d)/2;
    if(v[m]>k) --m;
    if(v[m]==k)
        return m;
    else
        return -1;
}

int cautare1(int s, int d, int k)
{
    int m;
    while(s<d)
    {
        m=(s+d)/ 2;
        if (v[m]<=k)
            s=m+1;
        else
            d=m;
    }
    m=(s+d)/2;
    if(v[m]>k) --m;
    return m;
}

int cautare2(int s, int d, int k)
{
    int m;
    while(s<d)
    {
        m=(s+d)/ 2;
        if (v[m]<k)
            s=m+1;
        else
            d=m;
    }
    m=(s+d)/2;
    if(v[m]<k) ++m;
    return m;
}

int main()
{
    int i, n, m, tip, val;
    in>>n;
    for(i=1;i<=n;++i)
        in>>v[i];
    in>>m;
    for(i=1;i<=m;++i)
    {
        in>>tip>>val;
        if(tip==0)
            out<<cautare0(1,n,val);
        else if(tip==1)
            out<<cautare1(1,n,val);
        else
            out<<cautare2(1,n,val);
        out<<'\n';
    }
    return 0;
}