#include <bits/stdc++.h>

#include <chrono>
using namespace std::chrono;
using namespace std;

   //declare global variables here
    int N, M;
    vector<int> v;
    vector<tuple<int, int>> questions;
    int binarySearch0(int x, int left, int right) {
       int mid,idx = -2;
       while(left <= right) {
           mid = left + (right-left)/2;
//printf("comp %d at %d\n", v[mid], mid);
           if(x == v[mid]) {
              idx = mid;
               left = mid + 1;
           }
            if(x < v[mid])
                right = mid - 1;
            if(x > v[mid])
                left = mid + 1;
       }
      
            return idx;
      
   }
     int binarySearch1(int x, int left, int right) {
       int mid, idx = -2;
       while(left <= right) {
           mid = left + (right-left)/2;
           if(mid >= N)
                return idx;
           if(v[mid] <= x) {
               idx = mid;
            //   printf("found %d at %d\n", v[mid], mid);
               left = mid + 1;
           }
           if(v[mid] > x) {
               right = mid - 1;
           }
       }
       return idx;
     }
     int binarySearch2(int x, int left, int right) {
       int mid, idx = -2;
       while(left <= right) {
           
           mid = left + (right-left)/2;
          // printf("comp %d at %d\n", v[mid], mid);
           if(v[mid] >= x) {
               idx = mid;
               right = mid - 1;
             //  printf("yes %d\n", idx);
           }
           else {
               left = mid + 1;
           }
       }
       return idx;
     }
    void print_output(int idx) {
        
        
    }
    void read_input() {
        ifstream fin("cautbin.in");
        fin >> N;
        int x, y;
       // printf("N = %d\n", N);
        for(int i = 0; i < N; i++) {
            fin >> x;
            v.push_back(x);
        }
        //  for(int i = 0; i < N; i++) {
        //      printf("%d ", v[i]);
        //  }
        
        fin >> M;
        for(int i = 0; i < M; i++) {
            fin >> x >> y;
            questions.push_back(make_tuple(x, y));
          //  printf("%d %d\n", x, y);
        }
       
        fin.close();
    }

    int get_result() {
        int idx = -1;
        ofstream fout("cautbin.out");
       for(int i = 0; i < M; i++) {
           int type = get<0>(questions[i]);
           int x = get<1>(questions[i]);
           switch(type) {
               case 0:
                    idx = binarySearch0(x, 0, N);
                    fout << (idx + 1);
                    fout << endl;
                    break;
                case 1:
                   // printf("SEARCH %d\n", x);
                    idx = binarySearch1(x, 0, N);
                    fout << (idx + 1) << endl;
                    break;
                case 2:
                    idx = binarySearch2(x, 0, N);
                    fout << (idx + 1) << endl;
                    break;
                default:
                    break;
           }
       }
       return idx;
    }


//
int main() {
    // auto start = high_resolution_clock::now();
    read_input();
    get_result();
    // auto stop = high_resolution_clock::now();
    // auto duration = duration_cast<milliseconds>(stop - start);
    // cout << duration.count() << endl;
    return 0;
}