// #include <iostream>
#include <fstream>
using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int main() {
      int m, n, a, b, mij = 0, st = 0, dr = 0, i, V[100005];
      cin >> n;
      for(i = 1; i <= n; i++)
            cin >> V[i];
      cin >> m;
      for(i = 0; i < m; i++) {
            cin >> b >> a;
            st = 1;
            dr = n;
            if(b == 0) {
                  while(st != dr) {
                        mij = (st + dr + 1) / 2;
                        if(V[mij] <= a)
                              st = mij;
                        else
                              dr = mij - 1;
                  }
                  if(V[st] == a)
                        cout << st << endl;
                  else
                        cout << -1 << endl;
            }
            else if(b == 1) {
                  while(st != dr) {
                        mij = (st + dr + 1) / 2;
                        if(V[mij] <= a)
                              st = mij;
                        else
                              dr = mij - 1;
                  }
                  cout << st << endl;
            }
            else if(b == 2) {
                  while(st != dr) {
                        mij = (st + dr) / 2;
                        if(V[mij] >= a)
                              dr = mij;
                        else
                              st = mij + 1;
                  }
                  cout << st << endl;
            }
      }
      return 0;
}//tema