#include <bits/stdc++.h>
using namespace std;



int v[100005];

int main()
{
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");
    int n, q, t, p;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>v[i];
    }
    cin>>q;
    for(int z=0; z<q; z++)
    {
        cin>>t>>p;
        if(t==0)
        {
            int pz=upper_bound(v, v+n, p)-v;
            if(v[pz-1]!=p)
                cout<<-1<<'\n';
            else
            {
                cout<<pz<<'\n';
            }
        }
        else if(t==1)
        {
            cout<<upper_bound(v, v+n, p)-v<<'\n';
        }
        else
        {
            cout<<lower_bound(v, v+n, p)-v+1<<'\n';
        }
    }
 
    return 0;
}