#include <iostream>
#include <fstream>
using namespace std;
int a[100000];

int cautare(int x,int i,int n)
{int m;
    m=(n+i)/2;
    while (a[m]!=x)
    {
        if (n==i) break;
        if (a[m]<x) i=m+1;
        else n=m-1;
        m=(n+i)/2;
    }
    return m;
}

int main()
{
    int n,i,m,x,y,k,l,o;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for (i=1;i<=n;i++) f>>a[i];
    f>>m;
    
    for (i=1;i<=m;i++)
    {f>>x>>y;
        k=cautare(y,1,n);
        if (a[k]==y)
        {
        for (l=k;l<n;l++) if (a[l]!=y) break;
        for (o=k;o>-1;o--) if (a[o]!=y) break;
            if (x==2) g<<o+1<<"\n";
            else g<<l-1<<"\n";}
        else
        { if (a[k]<y)
        {if (x==0) g<<-1<<"\n";
             else if (x==1) g<<k<<"\n";
            else g<<k+1<<"\n";
                   }
        else
        { if (x==0) g<<-1<<"\n";
            else if (x==1) g<<k-1<<"\n";
            else g<<k<<"\n";
        }
        }}
    f.close();
    g.close();
    return 0;
}