#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,v[100010];



int cb0(int s, int d, int val)

{

    int m;

    while(s <= d)

    {

        m = (s + d) / 2;

        if (v[m] <= val) s = m + 1;

        else d = m - 1;

    }

    m = (s + d) / 2;

    if (v[m] > val) m--;

    if (v[m] == val) return m;

    return -1;

}



int cb1(int s, int d, int val)

{

    int m, n = d;

    while(s < d)

    {

        m = (s + d) / 2;

        if (v[m] <= val) s = m + 1;

        else d = m;

    }

    m = (s + d) / 2;

    if (v[m] > val) m--;

    return m;

}



int cb2(int s, int d, int val)

{

    int m;

    while (s < d)

    {

        m = (s + d) / 2;

        if (v[m] < val) s = m + 1;

        else d = m;

    }

    m = (s + d) / 2;

    if (v[m] < val) m++;

    return m;

}



int main()

{

    int i, tip, val;

    f>>n;

    for (i = 1; i <= n; i++) f>>v[i];

    f>>m;

    for (i = 1; i <= m; i++)

    {

          f>>tip>>val;

          if (tip == 0) g<<cb0(1, n, val)<<'\n';

          if (tip == 1) g<<cb1(1, n, val)<<'\n';

          if (tip == 2) g<<cb2(1, n, val)<<'\n';

    }

    f.close();g.close();return 0;

}