#include <bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n, i, x, v[100001], m, nr;
int Binara0(int x, int st, int dr)
   { int m;
        while(st <= dr)
            {m = (st + dr)/2;
            if(v[m] <= x)
                st = m + 1;
            else
                dr = m - 1;
            }
    if(v[m] > x)
        m--;
    if(v[m] == x)
        return m;
    else return -1;

    }
int Binara1 (int x, int st, int dr)
    {
        int m;
        while(st <= dr)
            {m = (st + dr)/2;
            if(v[m] <= x)
                st = m + 1;
            else
                dr = m - 1;
            }
    m = (st + dr)/2;
    while(v[m] > x)
        m--;
    return m;
    }

int Binara2 (int x, int st, int dr)
    {
        int m;
        while(st <= dr)
            {m = (st + dr)/2;
            if(v[m] >= x)
                dr = m - 1;
            else
                st = m + 1;
            }
    m = (st + dr)/2;
    if(v[m] < x)
        m++;
    return m;
    }
int main()
{
    f>>n;
    for (i=1; i<=n; i++)
        f>>v[i];
    f>>m;
    for (i=1; i<=m; i++)
        {f>>nr>>x;
         if(nr == 0)
            g<<Binara0(x,1,n)<<endl;
         if(nr == 1)
            g<<Binara1(x,1,n)<<endl;
         if(nr == 2)
            g<<Binara2(x,1,n)<<endl;
        }

    return 0;
}