#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{
    int m,n,a,b,x,v[100001],p1,p2,p3,z,t,i;
    f>>n;
	p1=p2=-1;
    for(i=1;i<=n;++i)
        f>>v[i];
    f>>m;
    for(i=1;i<=m;++i)
    {
        f>>t>>z;
        p1=-1;
        p2=-1;
        p3=n+1;
        if(t%3==0)
        {
            a=1;
            b=n;
            x=(a+b)/2;
            while(a<=b)
            {
                if(v[x]==z)
                {
                    if(x>p1)p1=x;
                    a=x+1;
                }
                else
                {
                    if(v[x]<z)a=x+1;
                    else b=x-1;
                }
                x=(a+b)/2;
            }
            g<<p1<<endl;
        }
        else
        {
            if(t%3==1)
            {
                a=1;
                b=n;
                x=(a+b)/2;
                while(a<=b)
                {
                    if(v[x]<=z)
                    {
                        if(x>p2)p2=x;
                        a=x+1;
                    }                       
                    else
                    {
                        if(v[x]<z)a=x+1;
                        else b=x-1;
                    }
                    x=(a+b)/2;
                }
                g<<p2<<endl;
            }
            else
            {
				a=1;
				b=n;
				x=(a+b)/2;
				while(a<=b){
					if(v[x]>=z){
						if(x<p3)p3=x;
						b=x-1;
					}
					else a=x+1;
					x=(a+b)/2;
				}
				g<<p3<<endl;
			}
		}
	}
	f.close();
	g.close();
	return 0;
}