#include <fstream>
int v[100001];

using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int cautareBinara0 (int s, int d, int val) {
    int mij;

    while (s <= d) {
        mij = (s + d) / 2;
        if (v[mij] <= val)
            s = mij + 1;
        else
            d = mij - 1;
    }
    mij = (s + d) / 2;

    if (v[mij] > val) mij --;
    if (v[mij] == val)
        return mij;
    return -1;
}

int cautareBinara1 (int s, int d, int val) {
    int mij = d;

    while (s < d){
        mij = (s + d) / 2;
        if (v[mij] <= val)
            s = mij + 1;
        else
            d = mij;
    }

    mij = (s + d) / 2;
    if (v[mij] > val)
       -- mij;
    return mij;
}

int cautareBinara2 (int s, int d, int val) {
    int mij;

    while (s < d) {
        mij = (s + d) / 2;
        if (v[mij] < val)
            s = mij + 1;
        else
            d = mij;
    }

    mij = (s + d) / 2;
    if (v[mij] < val)
       ++ mij;
    return mij;
}

int main () {
    int i, n, m, op, x;

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

    f>>m;

    while (m )
        { f>>op>>x;
          switch (op)
      {case 0: {g<<cautareBinara0(1,n,x)<<"\n";break;}
      case 1: {g<<cautareBinara1(1,n,x)<<"\n";break;}
      case 2: {g<<cautareBinara2(1,n,x)<<"\n";break;}

        }
        m--;
        }
    return 0;
}