#include<iostream>
#include<vector>
#include<fstream>

using namespace std;


void solve(int format, int x, vector<int> arr, int left, int right, int &save) {

   
    if(right >= left) {
         int mid =  left + (right - left) / 2;

        if(format == 0) {
            if(arr[mid] == x && mid >= save) {
                save = mid + 1;
            }
                
            if(arr[mid] < x)
                solve(format, x, arr, left, mid - 1, save);    

            solve(format, x, arr, mid + 1, right, save);
        }
        else if(format == 1) {
            if(arr[mid] <= x && mid >= save)
                save = mid + 1;

            if(arr[mid] < x)
                solve(format, x, arr, left, mid - 1, save);   

            solve(format, x, arr, mid + 1, right, save);
        }
        else if(format == 2) {
            if(arr[mid] >= x && mid <= save) {
                save = mid;
            }

            if(arr[mid] < x)
                solve(format, x, arr, left, mid - 1, save);  

            solve(format, x, arr, mid + 1, right, save); 
        }
    }
    
}
int main() {


    int N; // numarul de elemente din vector
    int M; // numarul de intrebari la care trebuie sa raspunzi
            /*
                intrebari de forma:
                0 x - cel mai mare index pe care se afla x
                1 x - cel mai mare index pe care se afla un nr <= x
                2 x - cel mai mic index pe care se afla un nr >= x
           */

    vector<int> arr;

    ifstream input("cautbin.in");
    if( !input ) {
        perror("There was an errorn while opening the file!\n");
        exit(1);
    }

    ofstream output("cautbin.out");
    if( !output ) {
        perror("There was an error while opening the output file!\n");
        exit(2);
    }

    input >> N;
    int aux;
    for(int i = 0 ; i < N ; ++i) {
        input >> aux;
        arr.emplace_back(aux);
    }

    input >> M;
    
    int save = -1;
    int format, x;
    for(int i = 0 ; i < M ; ++i) {
         input >> format;
         input >> x;

         //cout << "format: " << format << "   x: " << x << "\n";

         solve(format, x, arr, 0, arr.size() - 1, save);
         output << save << "\n";
    }
    return 0;
}