#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,i,j,x,v[100005],lo,hi,mid,poz;
int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];
    fin>>m;
    for(i=1; i<=m; i++)
    {
        fin>>j>>x;
        poz=-1;
        lo=1;
        hi=n;
        if(j==0)
        {
            while(lo<=hi)
            {
                mid=lo+(hi-lo)/2;
                if(v[mid]>x)
                    hi=mid-1;
                if(v[mid]==x)
                {
                    poz=mid;
                    lo=mid+1;
                }
                if(v[mid]<x)
                    lo=mid+1;
            }
            fout<<poz<<"\n";
            continue;
        }
        if(j==1)
        {
            while(lo<=hi)
            {
                mid=lo+(hi-lo)/2;
                if(v[mid]>x)
                    hi=mid-1;
                else
                {
                    poz=mid;
                    lo=mid+1;
                }
            }

            fout<<poz<<"\n";
            continue;
        }
            while(lo<=hi)
            {
                mid=lo+(hi-lo)/2;
                if(v[mid]<x)
                    lo=mid+1;
                else
                {
                    poz=mid;
                    hi=mid-1;
                }
            }
            fout<<poz<<"\n";
    }
    return 0;
}