#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main()
{
    int n,x;
    fin >> n;
    int a[n+1];
    for (int i=1;i<=n;i++)
    {
        fin >> a[i];
    }
    fin >> x;

    for (int i=1;i<=x;i++)
    {
        int pb;
        int val;
        fin >> pb;
        fin >> val;
        int mid,ans,st,dr;
        st=1;
        dr=n;
        if(pb == 0)
        {
            ans = -1;
            while(st < dr)
            {
                mid = (st + dr)/2;
                if(a[mid] <= val)
                {
                    st = mid+1;
                    if(a[mid] == val) ans = mid;
                }
                else
                {
                    dr = mid;
                }
            }
            if (val==a[dr])
            {
                ans=dr;
            }
            fout << ans << endl;

        }
        else if (pb==1)
        {
            ans = -1;
            while (st<dr)
            {
                mid = (st + dr)/2+(st+dr)%2;
                if (a[mid]<=val)
                {
                    st=mid;
                    ans=mid;
                }else
                {
                    dr=mid-1;

                }
            }
            if (val>=a[st])
            {
                ans=st;
            }
            fout << ans << endl;
        }
        else
        {
            ans = -1;
            while(st < dr)
            {
                mid = (st + dr)/2;
                if(a[mid] < val)
                {
                    st = mid+1;
                    ans = mid;
                }
                else
                {
                    dr = mid;
                    //ans = mid;
                }
            }
            if(a[st] == val)
            {
                ans = st;
            }

            fout << ans << endl;
        }
    }
    return 0;
}