#include <iostream>
#include <fstream>
#define lmax 17
using namespace std;
 int v[100001];
int cautbin0(int n,int x){
  int r = 0, pas = 1 << lmax;
  while( pas != 0){
    if( r + pas <= n && v[r+pas] <= x)
      r+=pas;
    pas/=2;
  }
  return r;
}

int cautbin2(int n,int x){
  int r = 0, pas = 1 << lmax;
  while( pas != 0){
    if( r + pas <= n && v[r+pas] < x)
      r+=pas;
    pas/=2;
  }
  return r;
}

int main()
{
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");
    int n,m,cer,i,x,rez;
    cin>>n;
    for(i=1;i<=n;i++)
      cin>>v[i];
    cin>>m;
    for(i=0;i<m;i++){
      cin>>cer>>x;
      if(cer == 0){
        rez=cautbin0(n,x);
        if(v[rez] != x)
          rez=-1;
      }
      else if( cer == 1)
        rez=cautbin0(n,x);
      else
        rez=cautbin2(n,x)+1;
      cout<<rez<<endl;
    }
    return 0;
}