#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int a[200001];
int main()
{
    ifstream cin ("cautbin.in");
    ofstream cout ("cautbin.out");
    int n, T, y, x, l, r, mid;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
    }
    cin >> T;
    for(int i=1; i<=T; i++)
    {
        cin >> y >> x;
        if(y==0)
        {
            l=1;
            r=n+1;
            while(l<r)
            {
                mid=(l+r)/2;
                if(a[mid]<=x)
                    l=mid+1;
                else
                    r=mid;
            }
            if(a[l-1]!=x)
                cout << -1 << endl;
            else
                cout << l-1 << endl;
        }
        else if(y==1)
        {
            l=1;
            r=n+1;
            while(l<r)
            {
                mid=(l+r)/2;
                if(a[mid]<=x)
                    l=mid+1;
                else
                    r=mid;
            }
            cout << l-1 << endl;
        }
        else if(y==2)
        {
            l=1;
            r=n+1;
            while(l<r)
            {
                mid=(l+r)/2;
                if(a[mid]<x)
                    l=mid+1;
                else
                    r=mid;
            }
            cout << l << endl;
        }
    }
    return 0;
}