#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,i,m,cerinta,x,st,dr,mij,a,v[100100];
int main () {
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for (i=1;i<=m;i++) {
        fin>>cerinta>>a;
        if (cerinta==0) {
            st=1;
            dr=n;
            while (st<dr) {
                mij=(st+dr)/2;
                if (v[mij]>a) {
                    dr=mij-1;
                }
                if (v[mij]<a) {
                    st=mij+1;
                }
                if (v[mij]==a) {
                    x=mij;
                    break;
                }
            }
            while (v[x]==a)
                x++;
            fout<<x-1<<"\n";
        }
        if (cerinta==1) {
            st=1;
            dr=n;
            while (st<dr) {
                mij=(st+dr)/2;
                if (v[mij]>a) {
                    dr=mij-1;
                }
                if (v[mij]<=a) {
                    x=mij;
                    break;
                }
            }
            while (v[x]<=a)
                x++;
            fout<<x-1<<"\n";

        }
        if (cerinta==2) {
            st=1;
            dr=n;
            mij=0;
            while (st<dr) {
                mij=(st+dr)/2;
                if (v[mij]>=a) {
                    x=mij;
                    break;
                }
                if (v[mij]<x) {
                    st=mij+1;
                }
            }
            if (x!=0) {
                while (v[x]>=a)
                    x--;
                fout<<x+1<<"\n";
            }
            else
                fout<<-1<<"\n";

        }
    }
}