#include <bits/stdc++.h>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
void longest_position_same (int x, vector <int>v, int dr)
{
    int st = 0, mij, afs;
    bool ok=false;
    //fout<<dr<<endl;
    //while (st != dr && st!=dr-1 && st+1!=dr)
    while(st<=dr && ok==false)
    {
       // mij = st+(dr - st) / 2;
        mij=(st+dr)/2;
        if (v[mij] == x)
        {
            ok=true;
            while (v[mij] == v[mij + 1])
                mij++;
            fout << mij+1 << endl;
            //st = dr;
        }
        else
        {
            if (x > v[mij])
            {
                st = mij+1;
            }
            else
            {
                dr = mij-1;
            }
        }
    }
    if(ok==false)
    fout<<-1<<endl;
}

void second_task (int x, vector < int >v, int dr)
{
    int st = 0, mij;
    bool ok = false;
  //  while (st != dr && st!=dr-1 && st+1!=dr)
     while(st<=dr && ok==false)
    {
        mij = (dr+st) / 2;
        if (x == v[mij])
        {

            ok = true;
            while (v[mij] == v[mij + 1]){
                mij++;
            }
           // st = dr;
            fout << mij+1 << endl;

        } else if (x > v[mij])
        {
            st = mij+1;
        }
        else
            dr = mij-1;
    }
    if (ok == false)
    {
    fout<<st<<'\n';
    }
}
void third_task(int x, vector < int >v, int dr){
int st=0,mij;
bool ok=false;
//while(st!=dr && st+1!=dr && st!=dr-1){
   while(st<=dr && ok==false){
    mij=(dr+st)/2;
    if(x==v[mij]){
        ok=true;
        while (v[mij]==v[mij-1])
            mij--;
        fout<<mij+1<<'\n';
        st=dr;
    }
    else if(x>v[mij]){
        st=mij+1;
    }
    else
        dr=mij-1;
}
if(ok==false){
    fout<<st+1<<'\n';
}
}
int n, m, x, y, z;
vector < int >v;
int main ()
{
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        fin >> z;
        v.push_back (z);
    }
    fin >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        if (x == 0)
        {
            longest_position_same (y, v, n-1);
        }
        else if (x == 1)
        {
            second_task (y, v, n-1);
        }
        else{
third_task(y,v,n-1);
        }

    }
    return 0;
}