#include <algorithm>
#define input "cautbin.in"
#define output "cautbin.out"
#define DIM 100000

using namespace std ;

struct pachet
    {
        int x ;
        int y ;    
    } ;
int n ;
int v[DIM] ;
int m;
int mij ;
pachet a[DIM] ;
int k ;
void read() 
    {
        scanf ("%d" , &n) ;       
        for (int i=1 ; i<=n ;i++)
            {
                scanf ("%d" , &v[i]) ;    
            }
        scanf ("%d" , &m ) ;
        for (int i=1 ; i<=m ; i++)
            {
                scanf ("%d%d", &a[i].x , &a[i].y) ;    
            }
    }
    
int bin1(int t[DIM],int z)
    {
        int st=1 ;
        int dr=n ;
        while (st<dr)
            {
                mij=st+(dr-st)/2    ;
                if (t[mij]=z)
                    {
                        k=mij ;
                        while (t[k]==z)
                            {
                                k++ ;
                            }
                        return k-1 ;
                        
                    }
                if (z>mij)
                    st=mij+1 ;
                else
                    dr=mij-1 ;
            }    
        return -1 ;
    }
int bin2(int t[DIM],int z)
    {
        int st=1 ;
        int dr=n ;
        while (st<dr)
            {
                mij=st+(dr-st)/2    ;
                if (t[mij]=z)
                    {
                        k=mij ;
                        while (t[k]==z)
                            {
                                k++ ;
                            }
                        return k-1 ;
                        
                    }
                if (z>mij)
                    st=mij+1 ;
                else
                    dr=mij-1 ;
            }     
        if (t[mij]<z)
            return mij ;
        else
            return mij-1 ;
    }
int bin3(int t[DIM],int z)
    {
        int st=1 ;
        int dr=n ;
        while (st<dr)
            {
                mij=st+(dr-st)/2    ;
                if (t[mij]=z)
                    {
                        k=mij ;
                        while (t[k]==z)
                            {
                                k-- ;
                            }
                        return k+1 ;    
                    }
                if (z>mij)
                    st=mij+1 ;
                else
                    dr=mij-1 ;
            }        
        if (t[mij]<z)
            return mij+1 ;
        else
            return mij ;
    }

void solve()
    {
        
        for (int i=1 ; i<=m ; i++)
            {
                if (a[i].x==0)    
                    {
                        printf ("%d\n",bin1(v,a[i].y)) ;
                    }
                if (a[i].x==1)    
                    {
                        printf ("%d\n",bin2(v,a[i].y)) ;
                    }
                if (a[i].x==2)    
                    {
                        printf ("%d\n",bin3(v,a[i].y)) ;
                    }            
            }
    }

int main()
{
    freopen (input,"r",stdin) ;
    freopen (output,"w",stdout) ;
    
    read() ;
    solve() ;
    
    return 0;    
}