#include<fstream>
using namespace std;

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

const int N=1e5;
int v[N+1], rasp[N+1];

int main()
{
    int n, m, q, nr, p_2, h=0, l;
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i];
    for( p_2=1; p_2<=n; p_2 <<= 1);

    fin >> m;
    for(; m; --m)
    {
        fin >> q >> nr;
        if(q<2)
        {
            l=0;
            for(int j=p_2; j; j >>=1)
            {
                if(l+j<= n && v[l+j]<=nr)
                    l+=j;
            }
            if(!q && v[l]!=nr)
            {
                rasp[h]=-1;
                h++;
            }
            else
            {
                rasp[h]=l;
                h++;
            }
        }
        else
        {
            l=n;
            for(int j=p_2; j; j >>=1)
                if(l-j > 0 && v[l-j]>=nr)
                    l-=j;
            rasp[h]=l;
            h++;
        }
    }
    for(int i=0; i<=h-1; i++)
        fout << rasp[i] << "\n";
    return 0;
}