#include <bits/stdc++.h>
using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int v[100001];
int ct0bin(int val,int n)
{
    int pos=0;
    for(int msk=1<<20;msk>0;msk/=2)
        if(pos+msk<=n && v[pos+msk]<=val)
            pos+=msk;
        if(v[pos]==val)
            return pos;
        else
            return -1;
}
int ct1bin(int val,int n)
{
    int pos=0;
    for(int msk=1<<20;msk>0;msk/=2)
        if(pos+msk<=n && v[pos+msk]<=val)
            pos+=msk;
        if(v[pos]<=val)
            return pos;
}
int ct2bin(int val,int n)
{
    int pos=0;
    for(int msk=1<<20;msk>0;msk/=2)
        if(pos+msk<=n && v[pos+msk]<=val)
            pos+=msk;
        while(v[pos]==val)
            pos--;
        pos++;
            return pos;
}
int main()
{
     int n,i,m,c,x;
     in>>n;
     for(i=1;i<=n;i++)
        in>>v[i];
     in>>m;
     for(i=1;i<=m;i++)
     {
         in>>c>>x;
         if(c==0)
            out<<ct0bin(x,n)<<'\n';
         if(c==1)
            out<<ct1bin(x,n)<<'\n';
         if(c==2)
            out<<ct2bin(x,n)<<'\n';
     }

    return 0;
}