#include <stdio.h>
#include <stdlib.h>
#define Nmax 100010

using namespace std;
int v[Nmax];
int solve0(int p,int u,int x)
{
    int m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(v[m]<=x)
            p=m+1;
        else
            u=m-1;
    }
    m=(p+u)/2;
    if(v[m]>x)m--;
    if(v[m]==x)
        return m;
    return -1;
}
int solve1(int p,int u,int x)
{
    int m;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<=x)
            p=m+1;
        else
            u=m;
    }
    m=(p+u)/2;
    if(v[m]>x)
        m--;
    return m;
}
int solve2(int p,int u,int x)
{
    int m;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<x)
            p=p+1;
        else
            u=m;
    }
    m=(p+u)/2;
    if(v[m]<x)
       m++;
        return m;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n,t;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    { int tip,x;
      scanf("%d%d",&tip,&x);
      if(tip==0)
      printf("%d\n",solve0(1,n,x));
      if(tip==1)
      printf("%d\n",solve1(1,n,x));
      if(tip==2)
      printf("%d\n",solve2(1,n,x));
    }
    exit(0);
}