#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;//calculez mijlocul
        if ( v[mj] == b ){//daca am gasit elementul, mut st mai la dreapta
          rez = mj;
          st = mj + 1;
        }
        else if ( v[mj] < b )//daca a e in a doua jumatate, incep sa caut de acolo
          st = mj + 1;//mut st in a doua jumatate, dupa mijloc
        else//daca a e in prima jumatate, incep sa caut de acolo
          dr = mj - 1;//mut dr inainte de mijloc
      }
      fprintf( fout, "%d\n", rez );//in rez este ultima aparitie a lui b
    }
    else if ( a == 1 ){
      rez = -1;
      while ( st <= dr ){
        mj = ( st + dr ) / 2;
        if ( v[mj] <= b ){//daca mij nu este inca la b( b este in a doua jumatate ), sau a ajuns la el ( mij = b ), cresc st si incep sa caut rezultatul corect de la mij + 1
          rez = mj;
          st = mj + 1;
        }
        else //daca nu, mut dr la mj - 1, pentru ca inseamna ca este in prima jumatate si caut de acolo
          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 ){//daca b este in prima jumatate, mut dr la mj - 1 si incep sa caut de acolo
          rez = mj;
          dr = mj - 1;
        }
        else //daca este in a doua jumatate, mut st la mj + 1 si caut de acolo
          st = mj + 1;
      }
      fprintf( fout, "%d\n", rez );
    }
  }
  fclose ( fin );
  fclose ( fout );
  return 0;
}