#include<iostream.h>
#include<fstream.h>

int main(){
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int n, x;
    f>>n;
    int a[100010], i, j, st, dr, m, t, p;
    for (i = 1; i <= n; i++)
        f>>a[i];
    
    f>>p;
    for (i = 1; i <= p; i++){
        f>>t>>x;
        
        st = 1;
        dr = n;
        m = (st+dr)/2;
        
        while (st <= dr && a[m] != x){
            if (x < a[m])
                dr = m-1;
            else
                st = m+1;
            m = (st+dr)/2;
        }
        
        if (t == 0)
            if (a[m] != x)
                g<<-1<<'\n';
            else {
                while (m < n && a[m] == x)
                    m++;
                if (m == n && a[m] == x)
                    g<<m<<'\n';
                else 
                    g<<m-1<<'\n';   
            }
        else 
            if (t == 1){
                if (a[m] <= x){
                    while ( m < n && a[m] <= x)
                        m++;
                    if (m == n && a[m] <= x)
                        g<<m<<'\n';
                    else 
                        g<<m-1<<'\n';
                }
                else {
                    while (a[m] > x && m > 1)
                        m--;
                    g<<m<<'\n';
                }    
            }
            else {
                if (a[m] >= x){
                    while (a[m] >= x && m > 1)
                        m--;
                    if ( m == 1 && a[m] == x)
                        cout<<m<<'\n';
                    else
                        g<<m+1<<'\n';
                }
                else {
                    while (m < n && a[m] < x)
                        m++;
                    g<<m<<'\n';
                }    
            }
    }
    
    return 0;
}