#include<stdio.h>
int cautBin1(int v[], int inf, int sup, int cautat)
{
int mijloc;
while( inf <= sup)
{
mijloc = ( inf + sup)/2;
if( v[mijloc] <= cautat) // daca gasete valoarea marim limita inferioara pentru a vedea daca avem mai avem pe o poz, cu indice mai mare val cautata
inf = mijloc + 1;
else
sup = mijloc - 1;
}
mijloc = (inf + sup)/2;
//daca nu gaseste valoare pe o poz cu indice mai mare, decrementam mijlocul
if( v[mijloc] > cautat)
mijloc--;
if( v[mijloc] == cautat)
return mijloc;
return -1;
}
int cautBin2(int v[], int inf, int sup, int cautat)
{
int mijloc;
while( inf < sup)
{
mijloc = ( inf + sup)/2;
if( v[mijloc] <= cautat) // daca gasete valoarea marim limita inferioara pentru a vedea daca avem mai avem pe o poz, cu indice mai mare val cautata
inf = mijloc + 1;
else
sup = mijloc;
}
mijloc = (inf + sup)/2;
//daca nu gaseste valoare pe o poz cu indice mai mare, decrementam mijlocul
if( v[mijloc] > cautat)
--mijloc;
return mijloc;
}
int cautBin3(int v[], int inf, int sup, int cautat)
{
int mijloc;
while( inf < sup)
{
mijloc = ( inf + sup)/2;
if( v[mijloc] < cautat) // daca gasete valoarea marim limita inferioara pentru a vedea daca avem mai avem pe o poz, cu indice mai mare val cautata
inf = mijloc + 1;
else
sup = mijloc;
}
mijloc = (inf + sup)/2;
//daca nu gaseste valoare pe o poz cu indice mai mare, decrementam mijlocul
if( v[mijloc] < cautat)
++mijloc;
return mijloc;
}
int main()
{
FILE *inputFile, *outputFile;
inputFile=fopen("cautbin.in", "r");
outputFile=fopen("cautbin.out", "w");
int n,m, tip, v[100000],i, x;
int cautat1, cautat2, cautat3;
fscanf(inputFile, "%d", &n);
for(i=0; i<n; i++)
{
fscanf(inputFile, "%d", &v[i]);
}
fscanf(inputFile, "%d", &m);
for(i=0; i<m; i++)
{
fscanf(inputFile, "%d", &tip);
fscanf(inputFile, "%d", &x);
if( tip == 0)
{
cautat1 = cautBin1(v, 0, n-1, x);
fprintf(outputFile, "%d\n", cautat1 +1 );
}
if( tip == 1)
{
cautat2 = cautBin2(v, 0, n-1, x);
fprintf(outputFile, "%d\n", cautat2 +1 );
}
if( tip == 2)
{
cautat3 = cautBin3(v, 0, n-1, x);
fprintf(outputFile, "%d\n", cautat3 +1);
}
}
return 0;
}