#include <iostream>
#include <fstream>

using namespace std;

long n,m,v[100002];

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

long binary_search_up(long val,long query)
{long 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;
}

long binary_search_low(long val)
{long 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()
{long q,x;
f>>n;
for (long i=0;i<n;++i)
f>>v[i];
f>>m;
for (long 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;
}