#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

#define int long long

int arr[100001];

int32_t main()
{
    int n,q,cer,x;
    cin>>n;
    for (int i=1; i<=n; i++) cin>>arr[i];
    cin>>q;
    for (int i=1; i<=q; i++)
    {
        cin>>cer>>x;
        int s,r;
        if (cer==0)
        {
            s=1,r=n+1;
            while (s!=r)
            {
                int v=(s+r)/2;
                if (arr[v]>x) r=v;
                else s=v+1;
            }
            s=r=s-1;
            if (arr[s]==x) cout<<s<<endl;
            else cout<<-1<<endl;
        }
        else if (cer==1)
        {
            s=1,r=n+1;
            while (s!=r)
            {
                int v=(s+r)/2;
                if (arr[v]>x) r=v;
                else s=v+1;
            }
            cout<<s-1<<endl;
        }
        else
        {
            s=1,r=n+1;
            while (s!=r)
            {
                int v=(s+r)/2;
                if (arr[v]>=x) r=v;
                else s=v+1;
            }
            cout<<s<<endl;
        }
    }
}