#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream in ("cautbin.in") ;
ofstream out ("cautbin.out") ;

int main()
{
    int n , m ;
    in>> n ;
    vector<int> v(n + 1 , 0) ;
    for (int i = 1 ; i <= n ; i ++){
        in>> v[i] ;
    }
    in>> m ;
    for (int i = 1 ; i <= m ; i ++){
        int nrc , nr , c = 1 , f = n  , mij;
        in>> nrc >> nr ;
        if (nrc <= 1){
            while (f - c != 1) {
                mij = (c + f) / 2 ;
                if (nr >= v[mij])
                    c = mij ;
                else
                    f = m ;
            }
            if (nrc == 1)
                if(v[f] <= nr)
                    out<< f <<endl ;
                else
                    out<< c <<endl ;
            else
                if (v[f] == nr)
                    out<< f <<endl ;
                else
                    out<< -1 <<endl ;
        }
        else{
           while (f - c != 1) {
                mij = (c + f) / 2 ;
                if (nr <= v[mij])
                    f = mij ;
                else
                    c = mij ;
            }
            if(v[f] <= nr)
                out<< f <<endl ;
            else
                out<< c <<endl ;
        }
    }
    return 0;
}