#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
const int N = 100009;
int v[N],n,m,cer,x;
int cbexc(int val)
{
    int st = 1,dr = n,poz = -1;
    while(st<=dr)
    {
        int mij = (st+dr)>>1;
        if(v[mij]<=val)
            poz = mij,
            st = mij+1;
        else
            dr = mij-1;
    }
    if(v[poz]==val)return poz;
    return -1;
}
int lb(int val)
{
    int st =1,dr=n,poz = -1;
    while(st<=dr)
    {
        int mij = (st+dr)>>1;
        if(v[mij]<=val)
            poz = mij,
            st = mij+1;
        else
            dr = mij-1;
    }
    return poz;
}
int ub(int val)
{
    int st =1,dr=n,poz = -1;
    while(st<=dr)
    {
        int mij = (st+dr)>>1;
        if(v[mij]>=val)
            poz = mij,
            dr = mij-1;
        else
            st = mij+1;
    }
    return poz;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>v[i];
    cin>>m;
    while(m--)
    {
        cin>>cer>>x;
        if(cer==0)
            cout<<cbexc(x)<<'\n';
        else if(cer==1)
            cout<<lb(x)<<'\n';
        else
            cout<<ub(x)<<'\n';
    }
    return 0;
}
/*
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int MAX_SIZE = 100000;
int n, questions, v[MAX_SIZE + 10];

int binary_search_0 (int value) {
  int left = 1, right = n, position = -1;
  while (left <= right) {
    int middle = (left + right) >> 1;
    if (v[middle] <= value) {
      position = middle;
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  if (v[position] == value) {
    return position;
  }
  return -1;
}

int binary_search_1 (int value) {
  int left = 1, right = n, position = -1;
  while (left <= right) {
    int middle = (right + left) >> 1;
    if (v[middle] <= value) {
      position = middle;
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return position;
}

int binary_search_2 (int value) {
  int left = 1, right = n, position = -1;
  while (left <= right) {
    int middle = (right + left) >> 1;
    if (v[middle] >= value) {
      position = middle;
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return position;
}

int main() {
  fin >> n;
  for (int i = 1; i <= n; ++i){
    fin >> v[i];
  }
  fin >> questions;
  while(--questions) {
    int type, value;
    fin >> type >> value;
    if (type == 0) {
      fout << binary_search_0(value) << '\n';
    }
    if (type == 1) {
      fout << binary_search_1(value) << '\n';
    }
    if (type == 2) {
      fout << binary_search_2(value) << '\n';
    }
  }
  return 0;
}
*/