#include <fstream>
#include <cmath>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int x[100001];
int N,M,c,v;
int logN;
int ans;
void caut_bin(int val,int c,int aux)
{
 int i;
if(c<2)
{
    for(ans=logN,i=0;ans;ans>>=1)
    {
        if(i+ans<=N && x[i+ans]<=val)
            i+=ans;
    }
    if(x[i]!=val && c==1)
        cout<<-1<<endl;
    else
        cout<<i<<endl;
}
else
{
    for(ans=logN,i=N;ans;ans>>=1)
    {
        if(i-ans>0 && x[i-ans]>=val)
            i-=ans;
    }
    cout<<i<<endl;
}
}
int main()
{
    cin>>N;
    for(logN=1;logN<=N;logN<<=1);
    for(int i=1; i<=N; i++)
        cin>>x[i];
    cin>>M;
    for(int i=1; i<=M; i++)
    {
        cin>>c>>v;
        caut_bin(v,c,ans);
    }
    return 0;
}