#include <stdio.h>
#include <cstdio>
#define RRR ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long
 
#define pp pair<int,int>
using namespace std;
int ar[100001];
int n,low,high,mid;
 
int bina(int x)
{
     low = 1;
     high = n;
     
     
    while (low < high)
    {
         
         mid = low + high >> 1;
        if (ar[mid] > x)
            high = mid - 1;
        else
        {
             
            low = mid + 1;
        }
    }
    mid = low + high >> 1;
    if (ar[mid] == x)
        printf("%d\n",mid);
    else if (ar[mid-1] == x)
        printf("%d\n",mid-1);
    else printf("%d\n",-1);
    return 0;
}
 
int binar(int x)
{
     low = 1;
     high = n;
     
    while (low < high)
    {
        mid = low + high >> 1;
        if (ar[mid] > x)
            high = mid;
        else low = mid + 1;
    }
    mid = low + high >> 1;
    if (ar[mid] > x)
        mid--;
    printf("%d\n",mid);
    return 0;
}
 
int binar2(int x)
{
     low = 1;
     high = n;
      
    while (low < high)
    {
        mid = low + high >> 1;
        if (ar[mid] < x)
            low = mid+1;
        else high = mid;
    }
    mid = low + high >> 1;
    if (ar[mid] < x)
        mid++;
    printf("%d\n",mid);
    return 0;
}
 
int main()
{
     
//                                      freopen("text.txt","r",stdin);
        int i,j,q,a,x;
        freopen("cautbin.in","r",stdin);
        freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for ( i=1;i<=n;i++)
    {
         
        scanf("%d",&ar[i]);
    }
    //cout << bina(3);
     
    scanf("%d",&q);
    for ( i=0;i<q;i++)
    {
         
        scanf("%d%d",&a,&x);
        if (a == 0)
        {
            bina(x);
        }
        else if (a == 1)
        {
            binar(x);
             
        }
        else if (a == 2)
        {
            binar2(x);
        }
 
    }
    return 0;
  
}