#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100000];
int main()
{
    int n,m,x,p,i;
    in>>n;
    for(i=1; i<=n; i++)
        in>>v[i];
    in>>m;
    while(m--)
    {
        in>>p>>x;
        int 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
            {
                out<<mijl-1;;
            }
        }
        else
        {
            if(k)
            {
                i=k;
                while(v[i]==x)
                    i--;
                out<<i+1<<'\n';
            }
            else
            {
                out<<mijl;;
            }
        }
    }
    return 0;
}