#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out")
int x[100000],y,j,n,m;
int cautbin(int y1,int j1)
{
    int st=0,dr=n-1,mij,rasp=-1;
    if(j1==0)
    {
        while(st<=dr)
        {
          mij=(st+dr)/2;
          if(x[mij]==y1){st=mij+1;rasp=mij+1;}
          if(x[mij]>y1)dr=mij-1;
          if(x[mij]<y1)st=mij+1;
        }
        return rasp;
    }
    if(j1==1)
    {
        while(st<=dr)
        {
          mij=(st+dr)/2;
          if(x[mij]<=y1){st=mij+1;rasp=mij+1;}
          if(x[mij]>y1)dr=mij-1;
        }
        return rasp;
    }
    if(j1==2)
    {
        while(st<=dr)
        {
          mij=(st+dr)/2;
          if(x[mij]>=y1){dr=mij-1;rasp=mij+1;}
          if(x[mij]<y1)st=mij+1;
        }
        return rasp;
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
    }
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>j>>y;
        cout<<cautbin(y,j);
    }
    return 0;
}