#include <stdio.h>
#include <stdlib.h>

// functie care returneaza cea mai mare pozitie a lui x
// in vectorul v sau -1 daca nu se gaseste
int binary_search(int v[], int n, int x)
{
    int st = 1, dr = n, m, pos;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(x == v[m])
        {
            pos = m;
            break;
        }
        else if(x > v[m])
        {
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    if(st > dr)
    {
        return -1;
    }
    while(pos <= n - 1 && v[pos + 1] == x)
    {
        pos++;
    }
    return pos;
}

//functie care calc cea mai mare pozitie pe care se afla un elem cu val
//mai mica sau egala cu x
int upper_bound(int v[], int n, int x)
{
    int st = 1, dr = n, m, pos;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(x == v[m])
        {
            pos = m;
            break;
        }
        else if(x > v[m])
        {
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    if(st > dr)
    {
        return dr;
    }
    while(pos <= n - 1  && v[pos + 1] == x)
    {
        pos++;
    }
    return pos;
}

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

int main()
{
    FILE *in, *out;
    in = fopen("cautbin.in", "r");
    out = fopen("cautbin.out", "w");
    int n,v[100001],m,t,x;
    fscanf(in, "%d", &n);
    for(int i = 1; i <= n; i++)
    {
        fscanf(in, "%d", &v[i]);
    }
    fscanf(in, "%d", &m);
    for(int i = 1; i <= m; i++)
    {
        fscanf(in, "%d %d", &t, &x);
        if(t == 0)
        {
            fprintf(out, "%d\n", binary_search(v, n, x));
        }
        else if(t == 1)
        {
            fprintf(out, "%d\n", upper_bound(v, n, x));
        }
        else
        {
            fprintf(out, "%d\n", lower_bound(v, n, x));
        }
    }
    fclose(in);
    fclose(out);
    return 0;
}