#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<long long 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 = mij ;
                }
            }
            if (nrc == 1){
                if(v[f] <= nr){
                    out<< f << "\n" ;
                }
                else{
                    out<< c << "\n" ;
                }
            }
            else{
                if (v[f] == nr){
                    out<< f << "\n" ;
                }
                else{
                    if (v[c] == nr){
                        out<< c << "\n" ;
                    }
                    else{
                        out<< -1 << "\n" ;
                    }
                }
            }
        }
        else{
           while (f - c > 1) {
                mij = (c + f) / 2 ;
                if (nr <= v[mij])
                    f = mij ;
                else
                    c = mij ;
            }
            if(v[c] >= nr){
                out<< c << "\n" ;
            }
            else{
                out<< f << "\n" ;
            }
        }
    }
    return 0;
}