#include <iostream>
#include <vector>
using namespace std;

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