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

int n,v[maxIN];

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;

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    scanf("%d", &n);

    for(i=1; i<=n ;i++)
        scanf("%d", &v[i]);

    scanf("%d", &m);

    while(m--)
    {
          scanf("%d%d", &t, &x);

          switch(t)
          {
              case 0: printf("%d\n", case0(1,n,x));
              break;
              case 1: printf("%d\n", case1(1,n,x));
              break;
              case 2: printf("%d\n", case2(1,n,x));
              break;
          }
    }

    return 0;
}