/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 29, 2010, 8:40 AM
 */
#include <fstream>

/*
 *
 */
using namespace std;
int N, step;
int *v;
inline int max( int x, int y )
{
    return x^( (x^y) & -(x<y) );
}
inline int min( int x, int y )
{
    return y^( (x^y) & -(x<y) );
}
int Binary_Search( int option, int x )
{  
    int tidx, idx, i=0;
    if( 2 == option  )
        i=N;
    for( idx=step; idx; idx>>=1 )
    {
        if( option < 2 )
        {
            tidx=i+idx;
            if( tidx <= N && v[tidx] <= x )
                i=tidx;
            continue;
        }
        tidx=i-idx;
        if( tidx > 0 && v[tidx] >= x )
            i=tidx;
    }
    if( !option  &&  v[i] != x )
            i=-1;
    return i;
}
int main()
{int m, i, x, y;
    ifstream in("cautbin.in");
    in>>N;
    v=new int[N+1];
    for( step=0; step < N; step=1<<step );
    for( i=1; i <= N; ++i )
        in>>v[i];
    in>>m;
    ofstream out("cautbin.out");
    while( m-- )
    {
        in>>x>>y;
        out<<Binary_Search( x, y )<<'\n';
    }
    return 0;
}