#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
long long v[100005];
int main()
{
    long long n,m,x,p,i;
    in>>n;
    for(i=1; i<=n; i++)
        in>>v[i];
    in>>m;
    while(m--)
    {
        in>>p>>x;
        long long k=0,st=1,dr=n,mijl;
        while(st<=dr)
        {
            mijl=(st+dr)/2;
            if(x==v[mijl])
            {
                k=mijl;
                break;
            }
            else if(x<v[mijl])
                dr=mijl-1;
            else
                st=mijl+1;
        }
        if(p==0)
        {
            if(k==0)
                out<<-1<<'\n';
            else
            {
                i=k;
                while(v[i]==x)
                    i++;
                out<<i-1<<'\n';
            }
        }
        else if(p==1)
        {
            if(k)
            {
                i=k;
                while(v[i]==x)
                    i++;
                out<<i-1<<'\n';
            }
            else
            {
                if(v[mijl]<x)
                    out<<mijl<<'\n';
                else
                    out<<mijl-1<<'\n';
            }
        }
        else
        {
            if(k)
            {
                i=k;
                while(v[i]==x)
                    i--;
                out<<i+1<<'\n';
            }
            else
            {
                if(v[mijl]>x)
                    out<<mijl<<'\n';
                else
                    out<<mijl+1<<'\n';
            }
        }
    }
    return 0;
}