#include <bits/stdc++.h>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,v[100003],poz,m,t,x,poz1;
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(int i=1;i<=m;i++)
    {
        in>>t>>x;
        if(t==0)
        {
            int st,dr,ok=0;
            st=1;
            dr=n;
            while(st<=dr)
            {
                poz=(st+dr)/2;
                if(v[poz]==x)
                {
                    ok=1;
                  poz1=poz;
                  st=poz+1;
                }
                else if(v[poz]>x)dr=poz-1;
                else st=poz+1;
           }
        if(ok==0)out<<"-1"<<"\n";
        else out<<poz1<<"\n";
        }
        else if(t==1)
        {
            int st,dr;
            st=1;dr=n;
            while(st<=dr)
            {
                poz=(st+dr)/2;
                if(v[poz]<=x)
                {
                    poz1=poz;
                    st=poz+1;
                }
                else dr=poz-1;

            }
            out<<poz1<<"\n";
        }
        else
        {
            int st,dr,poz1;
            st=1;dr=n;
            while(st<=dr)
            {
                poz=(st+dr)/2;
                if(v[poz]>=x)
                {
                    poz1=poz;
                    dr=poz-1;
                }
                else st=poz+1;
            }
          out<<poz1<<"\n";
        }
    }
}