#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=0;
            while(s<=n)
            {
                m=(s+d)/2;
                if(a[m]==nr)
                {
                    p=m;
                    break;
                }
                else
                    if(a[m]<nr)
                    s++;
                    else
                    d--;
            }
            if(p==0)
                g<<-1<<"\n";
            else
            {
                while(a[p]==nr)
                    p++;
                p--;
                g<<p<<"\n";
            }
        }
        else
            if(v==1)
        {
            s=1;
            d=n;
            p=0;
            x=0;
            while(s<=d)
            {
                m=(s+d)/2;
                if(a[m]<=nr)
                {
                    x=a[m];
                    p=m;
                    s++;
                }
                else
                    d--;
            }
            while(a[p]==x)
                p++;
            p--;
            g<<p<<"\n";
        }
        else
        {
            s=1;
            d=n;
            p=0;
            x=0;
            while(s<=d)
            {
                m=(s+d)/2;
                if(a[m]>=nr)
                {
                    x=a[m];
                    p=m;
                    d--;
                }
                else
                    s++;
            }
            while(a[p]==x)
                p--;
            p++;
            g<<p<<"\n";
        }
    }

    return 0;
}