#include <stdio.h>
#include <stdlib.h>

int v[100000];

int main(){
    FILE *fin, *fout;
    fin = fopen ("cautbin.in", "r");
    fout = fopen ("cautbin.out", "w");
    int n, m, i, a, b, st, dr, mj, rez;
    fscanf(fin, "%d", &n);
    for (i = 1; i <= n; i++)
        fscanf(fin, "%d", &v[i]);
    fscanf(fin, "%d", &m);
    rez = 0;
    for (i = 0; i < m; i++)
    {
    fscanf(fin, "%d%d", &a, &b);
    st = 1;
    dr = n;
    if (a == 0)
    {
      rez = -1;
      while (st <= dr)
      {
        mj = (st + dr) / 2;
        if (v[mj] == b)
        {
          rez = mj;
          st = mj + 1;
        }
        else if (v[mj] < b)
          st = mj + 1;
        else
          dr = mj - 1;

      }
      fprintf(fout, "%d\n", rez);

    }
    else if (a == 1)
    {
        rez = -1;
      while (st <= dr)
      {
        mj = (st + dr) / 2;
        if ( v[mj] <= b )
        {
            rez = mj;
          st = mj + 1;

        }
        else
          dr = mj - 1;
      }
      fprintf(fout, "%d\n", rez);
    }
    else if (a == 2)
    {
      rez = -1;
      while (st <= dr){
        mj = (st + dr) / 2;
        if (v[mj] >= b)
        {
          rez = mj;
          dr = mj - 1;
        }
        else
          st = mj + 1;
      }
      fprintf(fout, "%d\n", rez);
    }
  }

  fclose (fin);
  fclose (fout);
  return 0;

}