#include <cstdio>

int binary_search0(int A[], int key, int imin, int imax)
{
    int imid;
    while(imin < imax)
    {
        imid = (imax + imin) / 2;
        if(A[imid] <= key)
            imin = imid + 1;
        else
            imax = imid - 1;
    }

    imid = (imax+imin)/2;

    if(A[imid] > key)
        imid--;
    if(A[imid] == key)
        return imid;
    return -1;
}

int binary_search1(int A[], int key, int imin, int imax)
{
    int imid;
    while(imin < imax)
    {
        imid = (imax + imin) / 2;
        if(A[imid] <= key)
            imin = imid + 1;
        else
            imax = imid;
    }

    imid = (imax+imin)/2;

    if(A[imid] > key)
        imid--;
    return imid;
}

int binary_search2(int A[], int key, int imin, int imax)
{
    int imid;
    while(imin < imax)
    {
        imid = (imax + imin) / 2;
        if(A[imid] < key)
            imin = imid + 1;
        else
            imax = imid;
    }

    imid = (imax+imin)/2;

    if(A[imid] < key)
        imid++;
    return imid;
}

int main()
{
    FILE * iFile;
    FILE * oFile;

    iFile = fopen("cautbin.in", "r");
    oFile = fopen("cautbin.out", "w");

    int i, n, m, q, qn, a[100001];

    fscanf(iFile, "%d", &n);

    for(i=1;i<=n;i++)
        fscanf(iFile, "%d", &a[i]);

    fscanf(iFile, "%d", &m);

    for(i=1;i<=m;i++)
    {
        fscanf(iFile, "%d %d", &q, &qn);
        if(q == 0)
            fprintf(oFile, "%d ", binary_search0(a, qn, 1, n));
        if(q == 0)
            fprintf(oFile, "%d ", binary_search1(a, qn, 1, n));
        if(q == 0)
            fprintf(oFile, "%d ", binary_search2(a, qn, 1, n));
    }

    fclose(iFile);
    fclose(oFile);

    return 0;
}