#include <bits/stdc++.h>

using namespace std;
ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
int a[100005],x,y,m,n;
int main()
{

    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for(int i=1;i<=m;i++)
       {
        fin>>x>>y;
    if(x==0)
    {
        x=upper_bound(a+1,a+n+1,y) -(a+1);
         if (a[x]==y && x!=1) fout<<x<< "\n";
         else fout<<"-1"<< "\n";
    }
    else
        if(x==1)
    {
        fout<<upper_bound(a+1,a+n+1,y) - (a+1)<< "\n";

    }
    else fout<<lower_bound(a+1,a+n+1,y) -a<< "\n";

       }
    return 0;
}