#include <fstream>
#define N 100005
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
long long a[N];
int n,m;
int Rezolva_0(int x, int st, int dr)
{
     bool gasit=false;
     int mj,poz;
     while(st<=dr && gasit==false)
      {
          mj=st+(dr-st)/2;
          if (x==a[mj])
           {
              gasit=true;
              poz=mj;
           }
          else if (x<a[mj])
                 dr=mj-1;
               else st=mj+1;
      }
     if (gasit==false) return -1;
     else {
            ///va trebui sa vad ultima pozitie a lui x
            while(a[poz]==x && poz<=n)
              poz++;
            return poz-1;
          }
}
int Rezolva_1(int x, int st, int dr)
{
    ///trebuie sa gasesc pozitia unde se afla primul x din vector
    bool gasit=false;
    int mj,poz;
    while(st<=dr && gasit==false)
     {
         mj=st+(dr-st)/2;
         if (x==a[mj])
          {
            gasit=true;
            poz=mj;
          }
         else if (x<a[mj]) dr=mj-1;
              else st=mj+1;
     }
     ///acum am pozitia poz, va trebuie sa il descresc pana la primul element x
     while(a[poz]<=x && poz<=n)
        poz++;
     poz-=1;
     return poz;
}
int Rezolva_2(int x, int st, int dr)
{
    bool gasit=false;
    int mj,poz;
    while(st<=dr && gasit==false)
     {
         mj=st+(dr-st)/2;
         if (x==a[mj])
          {
            gasit=true;
            poz=mj;
          }
         else if (x<a[mj]) dr=mj-1;
              else st=mj+1;
     }
    ///acum ca am pozitia unde se gaseste o valoare x,
    ///voi putea calcula ce mi se cere la cerinta 1
    while(a[poz]>=x && poz>=1)
       poz--;
    poz++;
    return poz;
}
int main()
{
    int i,val,x;
    cin>>n;
    for (i=1;i<=n;i++)
      cin>>a[i];
    cin>>m;
    for (i=1;i<=m;i++)
    {
        cin>>val>>x;
        /**
        daca val este 0, trebuie sa vad care este
        ultima pozitie de-a lui x (daca exista);
        daca nu exista, voi pune -1
        **/
        if (val==0)
           cout<<Rezolva_0(x,1,n)<<"\n";
        else if (val==1)
             cout<<Rezolva_1(x,1,n)<<"\n";
             else if (val==2)
                  cout<<Rezolva_2(x,1,n)<<"\n";
    }
    return 0;
}