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

int a[NMAX];
int main(void){
    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){
                    st = mid+1;
                }else if(a[mid] > y){
                    dr = mid-1;
                }else{
                    poz = mid + 1;
                    break;
                }
            }
            cout << poz + 1 << '\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-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 -1;
                }else{
                    st = mid + 1;
                }
            }
            cout << poz << '\n';
        }
    }

}