#include <bits/stdc++.h>

using namespace std;
int a[100005],x,y,m,n;
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    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<<y<<endl;
         else fout<<-1<<endl;
    }
    else
        if(x==1)
    {
        fout<<upper_bound(a+1,a+n+1,x) - (a+1) <<endl;

    }
    else fout<<lower_bound(a+1,a+n+1,x) -a<<endl;

       }
    return 0;
}