#include<fstream>
#include<algorithm>
#include<vector>
//#include<iostream>
using namespace std;
class InParser {
    vector<char> str;
    int ptr;
    ifstream fin;

    char getChar() {
        if (ptr == int(str.size())) {
            fin.read(str.data(), str.size());
            ptr = 0;
        }
        return str[ptr++];
    }

    template<class T>
    T getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + chr - '0';
            chr = getChar();
        }
        return sgn * num;
    }

public:
    InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
    ~InParser() { fin.close(); }

    template<class T>
    friend InParser& operator>>(InParser& in, T& num) {
        num = in.getInt<T>();
        return in;
    }
};
InParser cin("cautbin.in");
ofstream cout("cautbin.out");
int a[100002];
int cautare(int N,int val,int x)
{
   int i,step;

 if(x==0)
 {
     for(step=1;step<N;step<<=1);
     for(i=0;step;step>>=1)
         if((i+step)<N&&a[i+step]<=val)
             i+=step;
     if(a[i]==val)
     return i;
     return -1;

 }
 else
     if(x==1)
     {
         for(step=1;step<N;step<<=1);
         for(i=0;step;step>>=1)
             if((i+step)<N&&a[i+step]<=val)
             {i+=step;}

             return i;
     }
     else
     {
         for(step=1;step<N;step<<=1);
         for(i=0;step;step>>=1)
             if((i+step)<N&&a[step+i]<val)
             {i+=step;}
         if(a[i]==val)
             return i;
         return i+1;
     }
}
int main()
{
int n,x,m,y;
cin>>n;
for(int i=1;i<=n;i++)
    cin>>a[i];
cin>>m;
for(;m;m--)
{
    cin>>x>>y;
    cout<<cautare(n+1,y,x)<<'\n';

}
}