#include <fstream>
#include <iostream>
#define fin "cautbin.in"
#define fou "cautbin.out"
using namespace std;
long sir[100001];
int n,m;

int cbin0(int st,int dr,long x)
{
    if(st>dr) return 0;
    int p=(st+dr)/2;
    if(x==sir[p]) return p;
    else if(x>sir[p]) cbin0(st,p-1,x);
         else cbin0(st,p-1,x);
}

int cbin1(int st,int dr,long x)
{
    if(st>dr) return 0;
    int p=(st+dr)/2;
    if(st==dr)
        if(sir[st]>x) return st-1;
                 else return st;
    if(x==sir[p]) return p;
    else if(x>sir[p]) cbin1(p+1,dr,x);
         else cbin1(st,p,x);
}

int cbin2(int st,int dr,long x)
{
    if(st>dr) return 0;
    int p=(st+dr)/2;
    if(st==dr)
        if(sir[st]<x) return st+1;
                 else return st;
    if(x==sir[p]) return p;
    else if(x>sir[p]) cbin2(p+1,dr,x);
                 else cbin2(st,p,x);
}

int main()
{
    ifstream t1(fin);
    ofstream t2(fou);
    int i,j,mod,val,poz,ok;
    t1>>n;
    for(i=1;i<=n;i++) t1>>sir[i];
    t1>>m;
    for(i=1;i<=m;i++)
    {
        t1>>mod>>val;

        if(mod==0)
        {
            poz=cbin0(1,n,val);
            if(poz==0) t2<<"-1"<<'\n';
            else
            {
                while(sir[poz]==val) poz++;
                poz--;
                t2<<poz<<'\n';
            }
        }

        if(mod==1)
        {
            poz=cbin1(1,n,val);
            while(sir[poz]==val) poz++;
            poz--;
            t2<<poz<<'\n';
        }
        if(mod==2)
        {
            poz=cbin2(1,n,val);
            while(sir[poz]==val) poz--;
            poz++;
            t2<<poz<<'\n';
        }

    }
    t2.close();
    t2.close();
    return 0;
}