#include <fstream>
#define nmax 100001

using namespace std;

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


int n,m,a[nmax];

int Cautare0(int x)
{int s=1,d=n,m;
int poz=-1;
while(s<=d)
  {m=(s+d)/2;
   if(a[m]==x) {poz=m;break;}
   else
     if(x<a[m]) d=m-1;
     else s=m+1;
  }
if(poz==-1) return poz;
while(poz+1<=n&&a[poz]==a[poz+1]) poz++;
return poz;
}

int Cautare1(int x)
{int s=1,d=n,m;
int poz=-1;
while(s<=d)
  {m=(s+d)/2;
   if(a[m]<=x) {poz=m; s=m+1;}
   else d=m-1;
  }
return poz;
}

int Cautare2(int x)
{int s=1,d=n,m;
int poz=-1;
while(s<=d)
  {m=(s+d)/2;
   if(a[m]>=x) {poz=m; d=m-1;}
   else s=m+1;
  }
return poz;
}

void solutie()
{int i,x,v;
fin>>n;
for(i=1;i<=n;i++) fin>>a[i];
fin>>m;
for(i=1;i<=m;i++)
   {fin>>v>>x;
    if(v==0) fout<<Cautare0(x)<<"\n";
    if(v==1) fout<<Cautare1(x)<<"\n";
    if(v==2) fout<<Cautare2(x)<<"\n";
   }
}

int main()
{
    solutie();
    return 0;
}