#include <iostream>
#include <fstream>

#define nmax 100001

using namespace std;

int n, m;
int op, x;
int A[nmax];

int binarySearch(int lo, int hi, int x)
{
    
    int mid, pos = -1;
    
    while (lo <= hi)
    {
        mid = (lo + hi) >> 1;
        
        if (A[mid] == x)
            pos = mid;
        
        if (A[mid] > x)
            hi = mid - 1;
        else
            lo = mid + 1;
        
    }
    
    return pos;
    
}

int binarySearch1(int lo, int hi, int x)
{
    
    int mid, pos;
    
    while (lo <= hi)
    {
        
        mid = (lo + hi) >> 1;
        
        if (A[mid] <= x)
            pos = mid,
            lo = mid + 1;
        else
            hi = mid - 1;
        
    }
    
    return pos;
    
}

int binarySearch2(int lo, int hi, int x)
{
    
    int mid, pos;
    
    while (lo <= hi)
    {
        
        mid = (lo + hi) >> 1;
        
        if (A[mid] >= x)
            pos = mid,
            hi = mid - 1;
        else
            lo = mid + 1;
        
    }
    
    return pos;
    
}

int main()
{
    
    ifstream fi("cautbin.in");
    ofstream fo("cautbin.out");
    
    fi >> n;
    
    for (int i = 1; i <= n; i++)
        fi >> A[i];
    
    fi >> m;
    
    for (int i = 1; i <= m; i++)
    {
        fi >> op >> x;
        
        if (op == 0)
        {
            // cea mai mare pozitie pe care se afla x sau -1 daca nu exista
            fo << binarySearch(1, n, x) << "\n";
        }
        else if (op == 1)
        {
            // cea mai mare pozitie pe care se afla un element cu valoarea <= x
            fo << binarySearch1(1, n, x) << "\n";
        }
        else
        {
            // cea mai mica pozitie pe care se afla un element cu valoarea >= x
            fo << binarySearch2(1, n, x) << "\n";
        }
        
    }
    
    
    fi.close();
    fo.close();
    
    return 0;
}