#include <iostream>
#include <fstream>
using namespace std;
#define NMAX 100000
#define MMAX 100000;

int a[NMAX];
int main(void){
    ofstream cout("cautbin.out");
    ifstream cin("cautbin.in");
    int n,m;
    cin >> n;
    for(int i =0;i<n;i++){
        cin >> a[i];
    }
    cin >> m;
    int x,y;
    for(int i =0;i<m;i++){
        cin >> x >> y;
        if(x == 0){
            int dr = n-1;
            int st = 0;
            int poz = -1;
            int mid = 0;
            while(st <= dr){
                mid = (st+dr) / 2;
                if(a[mid] <= y){
                    poz = mid + 1;
                    st = mid+1;
                }else if(a[mid] > y){
                    dr = mid-1;
                }
            }
            mid = (st + dr) / 2;
            if(a[mid] > y)mid--;
            if(a[mid] == y)poz = mid+1;
            else poz = -1;
            cout << poz<< '\n';
        }
        if(x == 1){
            int dr = n-1;
            int st = 0;
            int poz = -1;
            int mid = 0;
            while(st <=dr){
                mid = (st+dr) / 2;
                if(a[mid]<=y){
                    poz = mid + 1;
                    st = mid + 1;
                }else{
                    dr = mid;
                }
            }
            mid = (st+dr)/2;
            if(a[mid] > y)mid--;
            poz = mid+1;
            cout << poz << '\n';
        }
        if(x == 2){ 
            int dr = n-1;
            int st = 0;
            int poz = -1;
            int mid = 0;
            while(st <=dr){
                mid = (st+dr) / 2;
                if(a[mid]>=y){
                    //poz = mid + 1;
                    dr = mid;
                }else{
                    st = mid + 1;
                }
            }
            mid = (st + dr) / 2;
            if(a[mid] < y)++mid;
            poz = mid+1;

            cout << poz << '\n';
        }
    }

}