#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, m, indice, val;
int v[100005];
void cautbin( int v[],int k, int st, int dr, int *maxim)
{
        int mij = (st + dr)/2;
        if (v[mij] == k)
            if (mij > *maxim)
                *maxim = mij;
        if (v[mij] <= k && st <= dr)
            cautbin(v, k, mij+1, dr, maxim);
        if (v[mij] >= k && st <= dr)
            cautbin(v, k, st, mij-1, maxim);
}
void cautbin1( int v[], int k, int st, int dr, int *maxim)
{
  int mij = (st + dr)/2;
  if ( v[mij] <= k && st <= dr)
  {
      *maxim = mij;
      cautbin1(v,k,mij+1,dr,maxim);
  }
  else
    if (st <= dr)
        cautbin1(v,k,st,mij-1,maxim);
}
void cautbin2( int v[], int k, int st, int dr, int *minim)
{
  int mij = (st+dr)/2;
  if ( v[mij]>=k && st <= dr)
  {
      *minim = mij;
      cautbin2(v,k,st,mij-1,minim);
  }
  else
    if (st <= dr)
        cautbin2(v,k,mij+1,dr,minim);
}
int main()
{
    fin>>n;
    int i;
    for (i = 1; i <= n ; i++)
        fin>>v[i];
    fin>>m;
    for (i = 1; i <= m; i++)
    {
        fin>>indice;
        fin>>val;
        int maxi = -1;
        switch (indice) {
            case 1 : cautbin1(v, val, 1, n, &maxi); fout<< maxi << '\n'; break;
            case 2 : cautbin2(v, val, 1, n, &maxi); fout<< maxi << '\n'; break;
            default : cautbin(v, val, 1, n, &maxi); fout << maxi << '\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}