#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,el[100010],m,t,x;

int binarysearch(int a,int b,int val)
{   while( a <= b )
    {   int m=(a+b)>>1;
        if( el[m] == val ) return m;
        else if( val < el[m] ) b=m-1;
        else a=m+1;
    }
    return -1;
}

int main()
{   f>>n; for(int i=1;i<=n;++i) f>>el[i];
    f>>m;
    while( m )
    {   f>>t>>x;
        if( t == 0 )
        {   if( binarysearch(1,n,x) == -1 ) g<<-1<<'\n';
            else
            {   for(int i=binarysearch(1,n,x); ;++i)
                    if( el[i] != el[i+1] ) {g<<i<<'\n'; break;}
            }
        }
        else if( t == 1 )
        {   if( binarysearch(1,n,x) == -1 )
            {   for(int i=1;i<=n;++i)
                    if( el[i] == x ) {g<<el[i-1]<<'\n'; break;}
            }
            else
            {   for(int i=binarysearch(1,n,x); ;++i)
                    if( el[i] != el[i+1] ) {g<<i<<'\n'; break;}
            }
        }
        else
        {   if( binarysearch(1,n,x) == -1 )
            {   for(int i=1;i<=n;++i)
                    if( el[i] > x ) {g<<el[i]<<'\n'; break;}
            }
            else
            {   for(int i=binarysearch(1,n,x); ;--i)
                    if( el[i] != el[i-1] ) {g<<i<<'\n'; break;}
            }
        }
        m--;
    }

g.close();
return 0;
}