#include <bits/stdc++.h>
#include <iostream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
const int maxn = 100000;
long long v[maxn+2];
int 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 )
    {
        int x;
        long long y;
        f >> x >> y;
        if( x == 0 )
        {
            int st = 1, dr = n;
            while( st < dr )
            {
                int mij = st + (dr-st)/2;
                ///[st, mij] si [mij+1, dr]
                if( v[mij+1] == y )
                    st = mij+1;
                else if( v[mij+1] > y )
                    st = mij+1;
                else
                    dr = mij;
            }
            if( v[st] == y )
                g << st << "\n";
            else
                g << -1 << "\n";
        }
        else if( x == 1 )
        {
            int st = 1, dr = n;
            while( st < dr )
            {
                int mij = st + (dr-st)/2;
                ///[st, mij] si [mij+1, dr]
                if( v[mij+1] <= y )
                    st = mij+1;
                else
                    dr = mij;
            }
            g << st << "\n";
        }
        else
        {
            int st = 1, dr = n;
            while( st < dr )
            {
                int mij = st + (dr-st)/2;
                ///[st, mij] si [mij+1, dr]
                if( v[mij] >= y )
                    dr = mij;
                else
                    st = mij+1;
            }
            g << st << "\n";
        }
    }
    return 0;
}