#include <bits/stdc++.h>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m, v[100001], x, p;

int cb(int a)
{
    int st=1, dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(a==v[mij])
            return mij;
        if(a<v[mij])
            dr=mij-1;
        if(a>v[mij])
            st=mij+1;
    }
    return -1;
}

int p0()
{
    int poz=cb(x);
    if(poz!=-1)
        for(int j=poz+1; j<=n && v[j]==x; j++)
            poz=j;
    return poz;
}

int p1()
{
    while(p0()==-1)
        x--;
    return p0();
}

int p2()
{
    int poz=cb(x);
    if(poz!=-1)
        for(int j=poz-1; j>=1 && v[j]==x; j--)
            poz=j;
    else
        for(int j=n; j>=1 && v[j]>x; j--)
            poz=j;
    return poz;
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>v[i];

    fin>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>p>>x;
        if(p==0)
            fout<<p0()<<'\n';
        else if(p==1)
            fout<<p1()<<'\n';
        else
            fout<<p2()<<'\n';
    }

    return 0;
}