#include <iostream>
#include <fstream>
using namespace std;

ifstream cinn("cautbin.in");
ofstream coutt("cautbin.out");



int main()
{
    int n, m, x, left, right, mid, y;
    cinn>>n;
    int v[n];
    for(int i = 1; i <= n; i++)
    {
        cinn>>v[i];
    }
    cinn>>m;
    for(int i = 1; i <= m; i++)
    {
        cinn>>y>>x;
        if(y == 0) // cazul 0
        {
            left = 1;
            right = n;
            while(left <= right)
            {
                mid = (left + right) / 2;
                if(v[mid] == x)
                {
                    coutt<<right-1<<endl;
                    break;
                }

                else if(x >= v[mid])
                {
                    left = mid+1;
                }
                else right = mid-1;

            }
            if(left > right) coutt<<-1<<endl;
        }

        if(y == 1) // cazul 1
        {
            left = 1;
            right = n;
            while(left <= right)
            {
                mid = (left + right) / 2;
                if(v[mid] <= x)
                {
                    left = mid + 1;
                }

                else
                {
                    right = mid - 1;
                }
            }
            coutt<<right<<endl;
        }

        if(y == 2) // cazul 2
        {
            left = 1;
            right = n;
            while(left <= right)
            {
                mid = (left + right) / 2;
                if(v[mid] < x)
                {
                    left = mid + 1;
                }

                else
                {
                    right = mid - 1;
                }
            }
            coutt<<left<<endl;
        }
    }
    cinn.close();
    coutt.close();
    return 0;
}