#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int N, M, v[100000];

int cautbin0(int nr)
{
    int st = 1, dr = N, mid;
    while(st < dr)
    {
        mid = (st + dr) / 2;
        if(v[mid] == nr && v[mid+1]!=nr)
            return mid;
        if(v[mid] > nr)
            dr = mid - 1;
        else
            st = mid + 1;
    }
    if(v[st] == nr)
        return st;
    return -1;
}

int cautbin1(int nr)
{
    int st = 1, dr = N, mid;
    while(st < dr)
    {
        mid = (st + dr) / 2;
        if(v[mid] <= nr && (v[mid+1] > nr || mid == N+1))
           return mid;
        if(v[mid] > nr)
            dr = mid - 1;
        else
            st = mid + 1;
    }
    if(v[st] <= nr)
        return st;
}

int cautbin2(int nr)
{
    int st = 1, dr = N, mid;
    while(st < dr)
    {
      mid = (st + dr) / 2;
      if(v[mid] >= nr &&(v[mid-1] < nr || mid == 0))
        return mid;
      if(v[mid] >= nr)
        dr = mid - 1;
      else
        st = mid + 1;
    }
    if(v[st]>=nr)
        return st;
}

int main()
{
    in >> N;
    for(int i = 1; i<=N; i++)
        in >> v[i];
    in >> M;
    for(int i = 1; i<=M; i++)
    {
        int x, y;
        in >> x >> y;
        if(x == 0)
        out << cautbin0(y) <<"\n";
        else if(x == 1)
        out << cautbin1(y) <<"\n";
        else
        out << cautbin2(y) <<"\n";
    }
}