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

#define maxInput 100005

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

int n,m,v[maxInput];

int bin(int p,int q,int x)
{
    int mij;
    if(p==q)
    {
        if(x==v[p]) return p;
        else return 0;
    }
    else
    {
        mij=(p+q)/2;
        if(x==v[mij]) return mij;
        else
        {
            if(x>v[mij])
            {
                bin(mij+1,q,x);
            }
            else
            {
                bin(p,mij-1,x);
            }
        }
    }
}

int main()
{
    int i,j,t,x,re,stop; f>>n;
    for(i=1; i<=n ;i++)
        f>>v[i];

    f>>m;
    for(i=1; i<=m ;i++)
    {
        f>>t; f>>x;
        switch(t)
        {
            case 0:
                    re=bin(1,n,x);
                    if(re)
                    {

                        stop=0; j=re;
                        while(j<=n && !stop)
                        {
                            if(v[j]!=x) stop=1;
                            else j++;
                        }
                        re=j-1;
                        g<<re<<endl;
                    }
                    else g<<-1<<endl;
            break;

            case 1:
                    if(v[n]<=x) g<<n<<endl;
                    else
                    {
                        re=bin(1,n,x);
                        stop=0; j=re;
                        while(j<=n && !stop)
                        {
                            if(v[j]!=x) stop=1;
                            else j++;
                        }
                        re=j-1;
                        g<<re<<endl;
                    }
            break;

            case 2:
                    if(v[1]>=x) g<<1<<endl;
                    else
                    {
                        re=bin(1,n,x);
                        stop=0; j=re;
                        while(j>1 && !stop)
                        {
                            if(v[j]!=x) stop=1;
                            else j--;
                        }
                        re=j+1;
                        g<<re<<endl;
                    }
            break;
        }
    }

    return 0;
}