#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream f("cautbin.in"); ofstream g("cautbin.out");
    int mij,l,n,m,i,j,x,k; int a[100001];
    f>>n;
    for(i=1;i<=n;i++) f>>a[i];
    f>>m;
    for(l=1;l<=m;l++)
    {
        f>>k>>x;
        i=1;
        j=n;
        while(i<=j)
        {
            mij=(i+j)/2;
            if (a[mij]==x) {while(a[mij+1]==x) {mij++;} break;}
            if (a[mij]<x) {i=mij+1;} else {j=mij-1;}
        }
        if((k==0) && (a[mij]==x)) {g<<mij<<'\n';} else {if (k==0) g<<-1<<'\n';}
        if(k==2) {while (a[mij]<x) {mij++;} while((a[mij]==x) && (a[mij-1]==x)) {mij--;} g<<mij<<'\n';}
        if(k==1) {while (a[mij]>x) {mij--;} g<<mij<<'\n';}
    }
    return 0;
}