#include <fstream>
using namespace std;
ifstream fi ("cautbin.in");
ofstream fo ("cautbin.out");
int i,n,q,x,tip;
int v[100006];
int cautbin0(int st,int dr,int val)
{
  if (st>dr) return -1;
  int mij=(st+dr)/2;
  if (v[mij]<val) return cautbin0(mij+1,dr,val);
  if (v[mij]>val) return cautbin0(st,mij-1,val);
  if (v[mij]==val and v[mij+1]==val) return cautbin0(mij+1,dr,val);
  else return mij;
}
int cautbin1(int st,int dr,int val)
{
  if (st>dr) return -1;
  int mij=(st+dr)/2;
  if (v[mij]>val) return cautbin1(st,mij-1,val);
  if (v[mij]<=val and v[mij+1]<=val) return cautbin1(mij+1,dr,val);
  else return mij;
}
int cautbin2(int st,int dr,int val)
{
  if (st>dr) return -1;
  int mij=(st+dr)/2;
  if (v[mij]<val) return cautbin2(mij+1,dr,val);
  if (v[mij]>=val and v[mij-1]>=val) return cautbin2(st,mij-1,val);
  else return mij;
}
int main()
{
    fi>>n;
    for (i=1;i<=n;i++) fi>>v[i];
    v[n+1]=(1<<31)-1;
    fi>>q;
    for (i=1;i<=q;i++)
    {
      fi>>tip>>x;
      if (tip==0) fo<<cautbin0(1,n,x)<<'\n';
      if (tip==1) fo<<cautbin1(1,n,x)<<'\n';
      if (tip==2) fo<<cautbin2(1,n,x)<<'\n';
    }
    return 0;
}