#include <bits/stdc++.h>

using namespace std;

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

int n,m,i,t[100001], s,d,mij,x,tip;

int main()
{
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>t[i];
    fin>>m;
    for (i=1;i<=m;i++)
    {
        fin>>tip>>x;
        if (tip==0)
        {
            s=1;
            d=n;
            int poz=-1;
            while (s<=d)
            {
                mij=(s+d)/2;
                if (x==t[mij])
                    poz=mij;
                    if (x>=t[mij])
                        s=mij+1;
                    else d=mij-1;
            }
            fout<<poz<<endl;
        }
        else if (tip==1)
        {
            s=1;
            d=n;
            int poz=-1;
            while (s<=d)
            {
                mij=(s+d)/2;
                if (x>=t[mij])
                    {
                        poz=mij;
                        s=mij+1;
                    }
                    else d=mij-1;
            }
            fout<<poz<<endl;
        }
        else
        {
            s=1;
            d=n;
            int poz=-1;
            while (s<=d)
            {
                mij=(s+d)/2;
                if (x<=t[mij])
                    {
                        poz=mij;
                        d=mij-1;
                    }
                    else s=mij+1;
            }
            fout<<poz<<endl;
        }
    }
    return 0;
}