#include <fstream>
#define NM 100005

using namespace std;

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

int be,en,mid,m,n,a[NM],i,op,nr,p,pd,ps;

int cautbin(int x)
{
    int be,en,mid;
    be=1;
    en=n;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (a[mid]==x)
          return mid;
        if (a[mid]>x)
          en=mid-1;
        else
          be=mid+1;
    }
    return en;
}

int main()
{
    fin >> n;
    for (i=1; i<=n; i++)
      fin >> a[i];
    fin >> m;
    for (i=1; i<=m; i++)
    {
        fin >> op >> nr;
        p=cautbin(nr);
        pd=p;
        ps=p;
        if (a[p]==nr)
        {
            while (a[pd]==nr)
              pd++;
            while (a[ps]==nr)
              ps--;
            if (op==0)
              fout << pd-1;
            if (op==1)
              fout << pd-1;
            if (op==2)
              fout << ps+1;
        }
        else
        {
            if (op==0)
              fout << -1;
            if (op==1)
            {
                if (nr>a[p])
                  fout << p;
                else
                  fout << p-1;
            }
            if (op==2)
            {
                if (nr>a[p])
                  fout << p+1;
                else
                  fout << p;
            }
        }
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}