#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

struct pereche {

    int first,second;
                } p[100001];

int N,M,a[100001],i,j,st,dr,mij,maxmin;
bool semafor;

int main()
{
    fin >> N;
    for (i=1;i<=N;++i)
    {
        fin >> a[i];
    }
    fin >> M;
    for (i=1;i<=M;++i)
    {
        fin >> p[i].first >> p[i].second;
        st=1;
        dr=N;
        semafor=0;
        while (st<=dr && semafor==0)
        {
            mij=(st+dr)/2;
            if (a[mij]==p[i].second)
            {
                semafor=1;
                while (a[mij]==p[i].second)
                {
                    ++mij;
                }
                --mij;
            }
            else if (a[mij]<p[i].second)
            {
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
        if (p[i].first==0)
        {
            if (semafor==1)
            {
                fout << mij;
            }
            else
            {
                fout << -1;
            }
            fout << '\n';
        }
        else if (p[i].first==1)
        {
            if (semafor==1)
            {
                fout << mij;
            }
            else
            {
                maxmin=INT_MIN;
                st=1;
                dr=N;
                while (st<=dr)
                {
                    mij=(st+dr)/2;
                    if (a[mij]<p[i].second && a[mij]>maxmin)
                    {
                        maxmin=a[mij];
                        while (a[mij]==maxmin)
                        {
                            ++mij;
                        }
                        --mij;
                    }
                    else
                    {
                        dr=mij-1;
                    }
                }
                fout << mij;
            }
            fout << '\n';
        }
        else
        {
            if (semafor==1)
            {
                while (a[mij]==p[i].second)
                {
                    --mij;
                }
                ++mij;
                fout << mij;
            }
            else
            {
                st=1;
                dr=N;
                maxmin=INT_MAX;
                while (st<=dr)
                {
                    mij=(st+dr)/2;
                    if (a[mij]>p[i].second && a[mij]<maxmin)
                    {
                        maxmin=a[mij];
                        while (a[mij]==maxmin)
                        {
                            --mij;
                        }
                        ++mij;
                    }
                }
                fout << mij;
            }
            fout << '\n';
        }
    }
    return 0;
}