//#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("cautbin.in");
ofstream cout("cautbin.out");
#define MAX 100010

int a[MAX];

int main()
{
    int n, i, m, x, y, ind;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
    }
    a[n+1]=1<<30;
    n++;
    fin>>m;
    while(m--)
    {
        fin>>x>>y;
        if(x==0)
        {
            ind=upper_bound(a+1, a+n+1, y)-a;
            if(a[ind-1]==y)
                cout<<ind-1;
            else
                cout<<-1;
        }
        if(x==1)
        {
            ind=upper_bound(a+1, a+n+1, y)-a;
            cout<<ind-1;
        }
        if(x==2)
        {
            ind=lower_bound(a+1, a+n+1, y)-a;
            cout<<ind;
        }
        cout<<"\n";
    }
}