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

int n, m, tip, x;
int v[MAX+1];

int main()
{
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> v[i];
    cin >> m;
    while(m--)
    {
        cin >> tip >> x;
        if(tip == 0)
        {
            int dr = upper_bound(v+1,v+1+n,x)-v-1;
            if(v[dr]!=x)cout << -1 << '\n';
            else cout << dr << '\n';
        }
        else if(tip == 1)
        {
            int dr = upper_bound(v+1,v+1+n,x)-v-1;
            cout << dr << '\n';
        }
        else
        {
            int st = lower_bound(v+1,v+1+n,x)-v;
            cout << st << '\n';
        }
    }
    return 0;
}