#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main()
{
    int x=-1,y=-1,z,m,n,i,w,v[100001],a,b,q,r;
    fin>>n;
    for(i=1;i<=n;i++)fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++){fin>>q>>r;
        x=-1;y=-1;z=n+1;
        if(q%3==0)
        {a=1;b=n;
            w=(a+b)/2;
            while(a<=b)
            {if(v[w]==r){if(w>x)x=w; a=w+1;}
                else
                {if(v[w]<r)a=w+1;else b=w-1;
                }
                w=(a+b)/2;
            }fout<<x<<'\n';
        }
        else
        {if(q%3==1)
            {a=1;b=n;
                w=(a+b)/2;
                while(a<=b)
                {if(v[w]<=r){if(w>y)y=w; a=w+1;}                       
                    else
                    {if(v[w]<r)a=w+1;else b=w-1;
                    }
                    w=(a+b)/2;
                }fout<<y<<'\n';
            }else
            {a=1;b=n;
                w=(a+b)/2;
                while(a<=b)
                {if(v[w]>=r){if(w<z)z=w;b=w-1; }
                    else a=w+1;
                    w=(a+b)/2;
                }fout<<z<<'\n';}
        }
    }
    fin.close();
    fout.close();
    return 0;
}