#include <iostream>
#include <fstream>

using namespace std;

int n,m,v[100000];

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

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

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;
t<<binary_search(x,q)<<'\n';
}
return 0;
}