#include<stdio.h>
#define dim 100111

int a[dim],n,m;

int caut1(int val )
{
    int st = 1 , dr = n , mid ;
    while ( st <=dr+1 )
    {
          mid = st + (dr-st)/2 ;
          if (a[ mid ] > val )
          dr = mid - 1 ;
          else
          if ( a[ mid ] < val )
          st = mid + 1;
          else
          if ( a[ mid ] == val)
          break; 
          }
    if ( a[mid] != val)
    return -1;
    while ( a[mid] == a[mid+1])
    mid ++;
    return mid ;
}
int caut3(int val )
{
    int st = 1 , dr = n , mid ;
    while ( st <=dr+1 )
    {
          mid = st + (dr-st)/2 ;
          if (a[ mid ] > val )
          dr = mid - 1 ;
          else
          if ( a[ mid ] < val )
          st = mid + 1;
          else
          if ( a[ mid ] == val)
          break; 
          }
          if ( a[mid] == val)
          while( a[mid-1 ] == val )
          mid --;
    if  ( a[ mid ] > val )
    return mid ;
    if  ( a[ mid ] < val )
    return mid + 1;  
    return mid ;
}
int caut2(int val )
{
    int st = 1 , dr = n , mid ;
    while ( st <=dr+1 )
    {
          mid = st + (dr-st)/2 ;
          if (a[ mid ] > val )
          dr = mid - 1 ;
          else
          if ( a[ mid ] < val )
          st = mid + 1;
          else
          if ( a[ mid ] == val)
          break; 
          }
    if ( a[ mid ] <= val)
    while ( a[ mid+1 ] <= val)
    mid ++;
    if ( a[ mid ] > val )
    while ( a[mid] > val )
    mid --;
    return mid ;
}
void solve()
{
     int t,val;
     scanf("%d",&n);
     for(int i=1 ; i<=n;i++)
     scanf("%d",&a[i]);
     scanf("%d",&m);
     for(int i=1 ; i<=m;i++)
     {
             scanf("%d%d",&t,&val );
             if ( t==0 )
             printf("%d\n",caut1( val ));
             if ( t==1 )
             printf("%d\n",caut2( val ));
             if ( t==2 )
             printf("%d\n",caut3( val ));
             }
return ;
}
int main ()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    solve();
    return 0;
}