#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100010],n,m,x,y;
int tip0 (int x)
{ int p=1,u=n,ans=-1,mid;
  while (p<=u)
  { mid=(p+u)/2;
    if (a[mid]<=x)
    { p=mid+1;
      if(a[mid]==x)
      ans=mid;
    }
    else u=mid-1;
  }
  return ans;
}
int tip1 (int x)
{ int p=1,u=n,mid,ans=-1;
    while (p<=u)
    { mid=(p+u)/2;
      if (a[mid]<=x)
      { ans=mid;
        p=mid+1;
      }
      else u=mid-1;
    }
    return ans;
}
int tip2 (int x)
{ int p=1,u=n,mid,ans=-1;
   while (p<=u)
   { mid=(p+u)/2;
     if (a[mid]>=x)
     { u=mid-1;
       ans=mid;
     }
     else p=mid+1;
   }
   return ans;
}
int main()
{ int i;
  f>>n;
  for (i=1;i<=n;i++)
  f>>a[i];
  f>>m;
  for (i=1;i<=m;i++)
  { f>>y>>x;
    if (y==0) g<<tip0(x)<<endl;
        if(y==1)  g<<tip1(x)<<endl;
    if (y==2) g<<tip2(x)<<endl;

  }

    return 0;
}