#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,a[100001];
int cautbin1(int x)
{
    int st=1,dr=n,m,p=-1;
    if(a[n]==x)return n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(x>a[m])st=m+1;
        else if(x<a[m])dr=m-1;
        else {p=m;st=m+1;}
    }
if(p)return p;
return -1;
}
int cautbin2(int x)
{
    int dr=n,st=1,m,p;
 if(a[n]>=x)return n;
    if(a[1]>=x)return 1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(x>=a[m]){p=m;st=m+1;}
        else dr=m-1;
    }
  return p;
}
int cautbin3(int x)
{
    int dr=n,st=1,m,p;
    if(a[n]<=x)return n;
    if(a[1]>=x)return 1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(a[m]>=x){p=m;dr=m-1;}
        else st=m+1;
    }
    return p;
}
int main()
{
    int s,i,x,y;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    fin>>s;
    while(s)
    {
        fin>>y>>x;
        if(y==0)fout<<cautbin1(x)<<" ";
        if(y==1)fout<<cautbin2(x)<<" ";
        if(y==2)fout<<cautbin3(x)<<" ";
        s--;
    }

    return 0;
}