#include <bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
const int maxn = 100000;
long long v[maxn+1], n, m;

int main() {
    f >> n;
    for( int i = 1; i <= n; ++i )
    {
        f >> v[i];
    }
    f >> m;
    for( int i = 1; i <= m; ++i )
    {
        long long x, y;
        f >> x >> y;
        if( x == 0 )
        {
            int st = 1, dr = n, ras = -1;
            while( st < dr )
            {
                int mij = st + (dr-st)/2;
                ///[st, mij] si [mij+1, dr]
                if( v[mij+1] == y )
                    st = mij+1, ras = mij+1;
                else if( v[mij+1] > y )
                    st = mij+1;
                else
                    dr = mij;
            }
            g << ras << "\n";
        }
        else if( x == 1 )
        {
            int st = 1, dr = n, ras = 1;
            while( st < dr )
            {
                int mij = st + (dr-st)/2;
                ///[st, mij] si [mij+1, dr]
                if( v[mij+1] <= y )
                    st = mij+1, ras = mij+1;
                else
                    dr = mij;
            }
            g << ras << "\n";
        }
        else
        {
            int st = 1, dr = n, ras = n;
            while( st < dr )
            {
                int mij = st + (dr-st)/2;
                ///[st, mij] si [mij+1, dr]
                if( v[mij] >= y )
                    dr = mij, ras = mij;
                else
                    st = mij+1;
            }
            g << ras << "\n";
        }
    }
}