#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");
int v[100000];
int main() {
    int n,m,p,nr,mij,st,dr,val;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>p>>nr;
        if(p==0)
        {
            st = 1; dr = n;
            while (st < dr)
            {
                // (7+1) / 2 = 4
                // (8+1) / 2 = 4
                int mij = (st + dr + 1) / 2;
                // daca a[mij] < val => st = mij+1
                // altfel dr = mij (a[mij] >= val)
                if (v[mij] <= nr) st = mij;
                else dr = mij-1;
            }
            if (v[st] <= nr) {
                fout<<st<<endl;
            }
            else fout << -1<<endl;
        }
        else if(p==1)
        {
            st = 1; dr = n;
            while (st < dr)
            {
                // (7+1) / 2 = 4
                // (8+1) / 2 = 4
                int mij = (st + dr + 1) / 2;
                // daca a[mij] < val => st = mij+1
                // altfel dr = mij (a[mij] >= val)
                if (v[mij] <= nr) st = mij;
                else dr = mij-1;
            }
            fout<<st<<endl;
        }
        else{
            st = 1; dr = n;
            while (st < dr)
            {
                int mij = (st + dr) / 2;

                if (v[mij] < nr) st = mij + 1;
                else dr = mij;
            }
            fout<<st<<endl;
        }
    }
    return 0;
}