#include <bits/stdc++.h>
#define DMAX 100005
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[DMAX],n, i, cer, m, k, x;
int main()
{fin >> n;
for(i = 1; i <= n; i++)fin >> v[i];
fin >> m;
for(k = 0; k < m; k++)
{fin >> cer >> x;
if(cer  == 0 || cer == 2)
{int st = 0, dr = n + 1;
while(dr - st > 1)
{int mij = (st + dr)/2;
if(v[mij] > x)dr = mij;
else st = mij;
}
if(cer == 0)
{if(st <= n && v[st] == x)fout << st << '\n';
else fout << -1 << '\n';
}
else
{
if((st <= n && v[st] == x) || st + 1 > n)fout << st << '\n';
else fout << st + 1 << '\n';
}
}
if(cer == 1)
{int st = 0, dr = n +1;
while(dr - st > 1)
{int mij = (st + dr)/2;
if(v[mij] >= x)dr = mij;
else st = mij;
}
if( (dr <= n && v[dr] == x) || dr - 1 < 1)fout << dr << '\n';
else fout << dr - 1 << '\n';
}
}
return 0;
}