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

class Task {
public:
    void solve() {
        read_input();
        print_output(get_result());
    }

private:
   //declare global variables here
    int N, M;
    vector<int> array;
    vector<tuple<int, int>> questions;

    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;
            array.push_back(x);
        }
        //  for(int i = 0; i < N; i++) {
        //      printf("%d ", array[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 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", array[mid], mid);
           if(x == array[mid]) {
              idx = mid;
               left = mid + 1;
           }
            if(x < array[mid])
                right = mid - 1;
            if(x > array[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(array[mid] <= x) {
               idx = mid;
               printf("found %d at %d\n", array[mid], mid);
               left = mid + 1;
           }
           if(array[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)/2;
          // printf("comp %d at %d\n", array[mid], mid);
           if(array[mid] >= x) {
               idx = mid;
               right = mid - 1;
             //  printf("yes %d\n", idx);
           }
           else {
               left = mid + 1;
           }
       }
       return idx;
     }
    void print_output(int idx) {
        
        
    }
};

//
int main() {
   auto* task = new (nothrow) Task(); // hint: cppreference/nothrow
    if (!task) {
        return -1;
    }
    task->solve();
    delete task;
    return 0;
}