#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m, v[100001];

int cautbin(int x){
    int m, li=1, lf=n;
    m = (li + lf) / 2;

    while(li <= lf && v[m] != x){
        if(v[m] > x)
            lf = m - 1;
        else
            li = m + 1;
        m = (li + lf) / 2;
    }
    if(v[m] == x)
        return m;
    return li;
}

int main()
{
    fin >> n;

    for(int i=1; i<=n; i++){
        fin >> v[i];
    }

    fin >> m;
    while(m){
        int k, x, aux;
        fin >> k >> x;
        aux = cautbin(x);
        if(v[aux] != x)
            if(k == 0)
                fout<<-1<<"\n";
            else
                if(k == 1)
                    fout<<aux+1<<"\n";
                else
                    fout<<aux<<"\n";
        else
            if(k == 0 || k == 1){
                while(aux <= n && v[aux] == x){
                    aux++;
                }
                fout<<aux-1<<"\n";
            }
            else{
                while(aux >= 1 && v[aux] == x){
                    aux--;
                }
                fout<<aux+1<<"\n";
            }

        m--;
    }

    return 0;
}