/*
forget binary search
ahahha
*/
#include <fstream>
#include <iostream>

using namespace std;

int n, *v;
int m;
int case0(int v[], int n, int x);
int case1(int v[], int n, int x);
int case2(int v[], int n, int x);

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int main() {
    fin >> n;
    v = new int[n];
    for (int i = 0; i < n; ++i) fin >> v[i];

    fin >> m;
    
    while (m--){
          int cod, x;
          fin >> cod >> x;
          switch (cod) {
                 case 0: fout << case0(v, n, x) << '\n'; break;
                 case 1: fout << case1(v, n, x) << '\n'; break;
                 case 2: fout << case2(v, n, x) << '\n'; break;
                 break;
                 }
          }    
    return 0;
    }
int case0(int v[], int n, int x) {
    int left = 0, right = n - 1;
    int sol = -2;
    if (v[right] < x || v[left] > x) return -1;
    while (left <= right) {
          if (x < v[left] || x > v[right]) break;  
          //(left, v[left])..(right, v[right])
          int dx = right - left;
          int dy = v[right] - v[left];
          //where is x
          // dy / dx
          int pos = left;         
          if (dy) pos = left + ((x - v[left]) * dx ) / dy;
          if (pos > right) pos = right;
          if (pos < left)  pos = left;

          if (v[pos] == x && (sol == -2 || pos > sol)) sol = pos;

          if (v[pos] <= x) left = pos + 1;
          else right = pos - 1;
          }
    return sol + 1;
    }
int case1(int v[], int n, int x) {
    int sol = -1;
    int left = 0, right = n - 1;
    while (left <= right) {
          //mai mic sau egal
//          if (sol != -1 && v[left] > sol) break;
          int dx = right - left;
          int dy = v[right] - v[left];
          //where is x
          int pos = left;
          if (dy) pos = left + ((x - v[left]) * dx) / dy;
          if (pos > right) pos = right;
          if (pos < left)  pos = left;
          if (v[pos] <= x && (sol == -1 || pos > sol)) sol = pos;
          if (v[pos] <= x) left = pos + 1;
          else right = pos - 1;
          }
    return sol + 1;
    }
int case2(int v[], int n, int x) {
    int sol = -1;
    int left = 0, right = n - 1;
    while (left <= right) {
        //  if (x < v[left] || x > v[right]) break;
        if (v[right] < x) break;
          int dx = right - left;
          int dy = v[right] - v[left];
          //where is x
          int pos = left;
          if (dy) pos = left + ((x - v[left]) * dx) / dy;
          if (pos < left)  pos = left;
          if (pos > right) pos = right;
          if (v[pos] >= x && (sol == -1 || pos < sol)) sol = pos;

          if (v[pos] <= x) left = pos + 1;         
          else right = pos - 1;
          }
    return sol + 1;
    }

  
/*
1 x -pozitia pe care se afla elementul cel mai mare mai mic sau egal cu x in sir.
     Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - pozitia pe care se afla elementul cel mai mic mai mare sau egal cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
*/