#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int cautare1(int nr);
int cautare2(int nr);
int cautare3(int nr);

int n;
int v[100001];

int main()
{
    int m;
    cin>>n;
    for(int i = 1; i <= n; ++i)
    {
        cin>>v[i];
    }
    cin>>m;
    while(m--)
    {
        int tip, x;
        cin>>tip>>x;
        if(tip == 0)
        {
            cout<<cautare1(x)<<"\n";

        }
        else if(tip == 1)
        {
            cout<<cautare2(x)<<"\n";
        }
        else
        {
            cout<<cautare3(x)<<"\n";
        }
    }

    return 0;
}


int cautare3(int nr)
{
    int st = 1, dr = n, rez = -1;
    while(st <= dr)
    {
        int mijl = (st + dr) / 2;
        if(v[mijl] < nr)
        {
            st = mijl + 1;
        }
        else
        {
            rez = mijl;
            dr = mijl - 1;
        }
    }
    return rez;
}

int cautare2(int nr)
{
    int st = 1, dr = n, rez = -1;
    while(st <= dr)
    {
        int mijl = (st + dr) / 2;

        if(v[mijl] <= nr)
        {
            rez = mijl;
            st = mijl + 1;
        }
        else
        {
            dr = mijl - 1;
        }
    }
    return rez;
}

int cautare1(int nr)
{
    int st = 1, dr = n, rez = -1;
    while(st <= dr)
    {
        int mijl = (st + dr) / 2;
        if(v[mijl] == nr)
        {
            rez = mijl;
            st = mijl + 1;
        }
        else if(v[mijl] > nr)
        {
            dr = mijl - 1;
        }
        else
        {
            st = mijl + 1;
        }
    }
    return rez;
}