#include <fstream>
#include <limits>
using namespace std;
long v[100001];
ifstream in("cautbin.in");
ofstream out("cautbin.out");
long binary_search(long x,long ls,long ld);
long search_exact(long x,long ls,long ld);
long search_less(long x,long ls,long ld);
long search_greater(long x,long ls,long ld);
int main()
{
long n,a,b,m,c;
in>>n;
in.ignore(numeric_limits<streamsize>::max(),'\n');
for(int i=0;i<n;++i)
{
in>>v[i];
}
in>>m;
in.ignore(numeric_limits<streamsize>::max(),'\n');
for(int i=0;i<m;++i)
{
in>>a>>b;
in.ignore(numeric_limits<streamsize>::max(),'\n');
switch (a)
{
case 0:
c=search_exact(b,0,n-1);
break;
case 1:
c=search_greater(b,0,n-1);
break;
case 2:
c=search_less(b,0,n-1);
break;
default:
return 0;
}
out<<c<<'\n';
}
in.close();
out.close();
return 0;
}
long search_less(long x,long ls,long ld)
{
long mid=(ls+ld)/2;
if (ls>ld) return search_less(v[mid],ls,ls);
if (x==v[mid])
{
while(v[mid]==x)
mid--;
return mid+2;
}
else if (x<v[mid])
{
return search_exact(x,ls,mid-1);
}
else
{
return search_exact(x,mid+1,ld);
}
return -1;
}
long search_greater(long x,long ls,long ld)
{
long mid=(ls+ld)/2;
if (ls>ld) return search_greater(v[mid],ls,ls);
if (x==v[mid])
{
while(v[mid]==x)
mid++;
return mid;
}
else if (x<v[mid])
{
return search_exact(x,ls,mid-1);
}
else
{
return search_exact(x,mid+1,ld);
}
return -1;
}
long search_exact(long x,long ls,long ld)
{
if (ls>ld) return -1;
long mid=(ls+ld)/2;
if (x==v[mid])
{
while(v[mid]==x)
mid++;
return mid;
}
else if (x<v[mid])
{
return search_exact(x,ls,mid-1);
}
else
{
return search_exact(x,mid+1,ld);
}
return -1;
}