#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
int main()
{
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    int m;
    fin >> m;
    for(int i = 1; i <= m; i++)
    {
        int t, x;
        fin >> t >> x;

        if(t == 0)
        {
            int l = 1;
            int r = n;

            while(l <= r)
            {
                int mid = (l + r) / 2;
                if(x >= v[mid])
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }
            int mid = (l + r) / 2;
            if(v[mid] > x)
            {
                mid--;
            }
            if(v[mid] == x)
            {
                fout << mid;
            }
            else
            {
                fout << "-1";
            }
            fout << "\n";
        }

        else if(t == 1)
        {
            int l = 0;
            int r = n;
            while(l < r)
            {
                int mid = (l + r) / 2;
                if(x >= v[mid])
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid;
                }
            }

            int mid = (l + r) / 2;
            if(v[mid] > x)
            {
                mid--;
            }
            fout << mid;
            fout << "\n";
        }
        else
        {
            int l = 0;
            int r = n;
            while(l < r)
            {
                int mid = (l + r) / 2;
                if(x > v[mid])
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid;
                }
            }
            int mid = (l + r) / 2;
            if(v[mid] < x)
            {
                mid++;
            }
            fout << mid;
            fout << "\n";
        }
    }
    return 0;
}