#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,i,t,v,nr,a[100005],p,s,d,m,x;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>v>>nr;
        if(v==0)
        {
           s=1;
           d=n;
           p=-1;
           while(s<=d)
           {
            m=(s+d)/2;
                if(a[m]==nr)
                    p=m,s=m+1;
            else
                if(a[m]<nr)
                    s=m+1;
            else
                d=m-1;
           }
        g<<p<<"\n";
        }
        else
            if(v==1)
        {
            s=1;
            d=n;
            p=-1;
            while(s<=d)
            {
                m=(s+d)/2;
                if(a[m]<=nr)
                {
                    p=m;
                    s=m+1;
                }
                else
                    d=m-1;
            }
            g<<p<<"\n";
        }
        else
        {
            s=1;
            d=n;
            p=0;
            x=0;
            while(s<=d)
            {
                m=(s+d)/2;
                if(a[m]>=nr)
                {
                    p=m;
                    d=m-1;
                }
                else
                    s=m+1;
            }
            g<<p<<"\n";
        }
    }

    return 0;
}