#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,m,a[100010],op,x;

int cautbin0(int x)
{
  int st = 1, dr = n, mij;
   while(st<=dr)
   {
     mij=(st+dr)/2;

     if(a[mij]==x)break;

     if(x>a[mij])
      st=mij+1;
      else
      dr=mij-1;
   }

   if(a[mij]!=x)return -1;

   while(a[mij]==a[mij+1])
   {
    mij++;
   }

   return mij;
}

int cautbin1(int x)
{
  
  int st = 1, dr = n, mij;
   while(st<=dr)
   {
     mij=(st+dr)/2;

     if(x>a[mij])
      st=mij+1;
      else
      dr=mij-1;
   }

    while(a[mij]>=a[mij+1])
   {
     mij++;
   }

   return mij;
}

int cautbin2(int x)
{
   int st = 1, dr = n, mij;
   while(st<=dr)
   {
     mij=(st+dr)/2;

     if(x>a[mij])
      st=mij+1;
      else
      dr=mij-1;
   }

   while(a[mij]<=a[mij-1])
   {
     mij--;
   }

   return mij;
}


int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
     fin>>a[i];

    fin>>m;

    for(int i=1; i<=m; i++)
    {
       fin>>op;
       fin>>x;

       if(op==0)
       {
         fout<<cautbin0(x)<<endl;
       }
       else
       if(op==1)
       {
         fout<<cautbin1(x)<<endl;
       }
       else
       if(op==2)
       {
         fout<<cautbin2(x)<<endl;
       }
    }
}