#include <iostream>
#include <fstream>

using namespace std;

int n,m,v[100000];

ifstream f ("cautbin.in");
ofstream t ("cautbin.out");

int binary_search_up(int val,int query)
{int i, step;
for (step = 1; step < n; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < n and v[i + step] <= val)
i += step;
if (query==0){
if (v[i]!=val) i=-2;}
return i+1;
}

int binary_search_low(int val)
{int i, step;
for (step = 1; step < n; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < n and v[i + step] < val)
i += step;
return i+2;
}

int main()
{int q,x;
f>>n;
for (int i=0;i<n;++i)
f>>v[i];
f>>m;
for (int i=0;i<m;++i){
f>>q>>x;
if (q==0 or q==1)
t<<binary_search_up(x,q)<<'\n';
else
t<<binary_search_low(x)<<'\n';
}
return 0;
}