#include <fstream>
using namespace std;
int v[100005], n, inc, sf, mid, best;
ofstream out ("cautbin.out");
void afis (int rez)
{
    out << rez << '\n';
}
int solve0 (int x)
{
   best = 0;
   inc = 1;
   sf = n;
   while (inc <= sf)
   {
       mid = (inc + sf) / 2;
       /*if (v[mid] == x)
       {
           for (i = mid + 1; i <= sf; ++i)
           if (v[i] != x)
           return i-1;
       }
       else
       if (v[mid] < x)
       inc = mid + 1;
       else
       sf = mid -1;*/
       if (v[mid] == x && mid >= best)
       {
           best = mid;
           inc = mid + 1;
       }
       else
       if (v[mid] > x)
       sf = mid - 1;
       else
       inc = mid +1;
   }
   if (best == 0)
   return -1;
   else
   return best;
}
int solve1 (int x)
{
    best = 0;
    inc = 1;
    sf = n;
    while (inc <= sf)
    {
        mid = (inc + sf) / 2;
        if (v[mid] <= x && mid >= best)
        {
            best = mid;
            inc = mid+1;
        }
        else
        sf = mid - 1;
    }
    return best;
}
int solve2 (int x)
{
    best = 100001;
    inc = 1;
    sf = n;
    while (inc <= sf)
    {
        mid = (inc + sf) / 2;
        if (v[mid] >= x && mid <= best)
        {
            best = mid;
            sf = mid - 1;
        }
        else
        inc = mid + 1;
    }
    return best;
}
void solve ()
{
    int rez, x, y, m, i;
    ifstream in ("cautbin.in");
    in >> n;
    for (i = 1; i <= n; ++i)
    in >> v[i];
    in >> m;
    for (i = 1; i <= m; ++i)
    {
        in >> y >> x;
        if (y == 0)
        rez = solve0 (x);
        if (y == 1)
        rez = solve1 (x);
        if (y == 2)
        rez = solve2 (x);
        afis (rez);
    }
    in.close ();
}
int main()
{
    solve ();
    out.close ();
    return 0;
}