#include <iostream>
#include <fstream>
#define maxIN 100005
using namespace std;

int n,v[maxIN];
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int case0(int p, int q, int x)
{
    int mid;

    while(p<=q)
    {
        mid=(p+q)/2;
        if(v[mid]<=x)
            p=mid+1;
        else
            q=mid-1;
    }
    mid=(p+q)/2;

    if(v[mid]>x) mid--;
    if(v[mid]==x) return mid;
    return -1;
}

int case1(int p, int q, int x)
{
    int mid;

    while(p<q)
    {
        mid=(p+q)/2;
        if(v[mid]<=x)
            p=mid+1;
        else
            q=mid;
    }

    mid=(p+q)/2;
    if(v[mid]>x) --mid;
    return mid;
}

int case2(int p, int q, int x)
{
    int mid;

    while(p<q)
    {
        mid=(p+q)/2;
        if(v[mid]<x)
            p=mid+1;
        else
            q=mid;
    }

    mid=(p+q)/2;
    if(v[mid]<x) ++mid;
    return mid;
}

int main()
{
    int i,n,m,t,x;
    f>>n;

    for(i=1; i<=n ;i++)
        f>>v[i];

   f>>m;

    while(m--)
    {
          f>>t; f>>x;

          switch(t)
          {
              case 0: g<<case0(1,n,x)<<endl;
              break;
              case 1: g<<case1(1,n,x)<<endl;
              break;
              case 2: g<<case2(1,n,x)<<endl;
              break;
          }
    }

    return 0;
}