#include <bits/stdc++.h>
using namespace std;

int a[100000];

int cb1(int x, int n){
    int st = 0;
    int dr = n-1;
    int poz = -1;
    int mid =0;
    while(st <= dr){
        mid = (st+dr) / 2;
        if(a[mid] == x){
            poz = mid+1;
            st = mid + 1;
        }
        else if(a[mid] < x){
            st = mid+1;
        }else{
            dr = mid-1;
        }
    }
    return poz;
}

int cb2(int x, int n){
    int st = 0;
    int dr = n-1;
    int poz = -1;
    int mid =0;
    while(st <= dr){
        mid = (st+dr) / 2;
        if(a[mid] <= x){
            poz = mid+1;
            st = mid+1;
        }
        if(a[mid] > x){
            dr = mid-1;
        }
    }
    return poz;
}

int cb3(int x, int n){
    int st = 0;
    int dr = n-1;
    int poz = -1;
    int mid =0;
    while(st <= dr){
        mid = (st+dr) / 2;
        if(a[mid] >= x){
            poz = mid+1;
            dr = mid-1;
        }
        else{
            st = mid+1;
        }
    }
    return poz;
}


int main(void){
    ofstream cout("cautbin.out");
    ifstream cin("cautbin.in");
    int n;
    cin >> n;
    for(int i =0;i<n;i++){
        cin >> a[i];
    }
    int q;
    cin >> q; 
    for(int i =0;i<q;i++){
        int x,y;
        cin >> y >> x;
        if(y == 0)
         cout << cb1(x,n) << "\n";
        else if(y == 1)
         cout << cb2(x,n) << "\n";
        else if(y == 2)
         cout << cb3(x,n) << "\n";

    }
}