# include <fstream>
using namespace std;
int n, m, a[100005]; 
struct tip {
       int x, q;};
tip b[100005];
ofstream fout ("cautbin.out");
void citire ()
{
     int i;
     ifstream fin ("cautbin.in");
     fin>>n;
     fout<<n<<endl;
     for (i=1;i<=n;i++)
         fin>>a[i], fout<<a[i]<<" ";
     fin>>m;fout<<endl<<m<<endl;
     for (i=1;i<=m;i++)
         fin>>b[i].q>>b[i].x, fout<<b[i].q<<" "<<b[i].x<<endl;
}
int caut (int x, int st, int dr, int caz)
{
    int mid;
    mid=st/2+dr/2;
    if (st==dr && a[st]!=x)
       return -1;
    if (a[mid]==x)
    {   
       if (caz==0)
       {   
          while (a[mid]==x && mid<=n)
                mid++;
          return mid-1;
       }
       else
           if (caz==1)
           {
              while (a[mid]==x && mid>0)
                   mid--;
              if (mid==0)
                 return mid+1;
              else
                  return mid;
           }
           else
               if (caz==2)
               {
                   while (a[mid]==x && mid<=n)
                         mid++;
                    if (mid==n+1)
                       return mid-1;
                    else
                       return mid;
               }
    }
    else
        if (x<a[mid])
           return caut(x, st, mid, caz);
        else
            if (x>a[mid])
               return caut (x, mid, dr, caz);
}      
int main ()
{
    int i;
    citire ();
    for (i=1;i<=m;i++)
        fout<<caut(b[i].x, 1, n, b[i].q)<<endl;
     return 0;
}