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

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,m,a[100005];

int cautbin(int x, int c, int lg)
{
    int poz=0;

    for(int i=0;lg!=0;lg>>=1)
    {
        if(i+lg<n && a[i+lg]<=x)
        {
            poz=i+lg;
            i+=lg;
        }
    }

    if(a[poz]!=x && c==0)
        return -1;

    return (poz+1);
}

int cautbincaz3(int x, int lg)
{
    int poz=n-1;

    for(int i=n-1;lg!=0;lg>>=1)
    {
        if(i-lg>=0 && a[i-lg]>=x)
        {
            poz=i-lg;
            i-=lg;
        }
    }

    return (poz+1);
}

int main()
{
    f>>n;

    int lg=1;

    for(lg=1;lg<=n;lg<<=1);

    for(int i=0;i<n;i++)
        f>>a[i];

    f>>m;

    int x,c;

    for(int i=0;i<m;i++)
    {
        f>>c>>x;

        if(c<2)
            g<<cautbin(x,c,lg)<<"\n";
        else
            g<<cautbincaz3(x,lg)<<"\n";
    }

    return 0;
}