#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

FILE *fin, *fout;
long n, m, tip, a[100010], numar;

int Cauta(int type, int val)
{  
    int lo = 0, hi = n-1, mid;
    if (type == 0)
    {        
         while (lo < hi)
         {
             mid = lo + (hi - lo)/2;
             if (a[mid] == val)
             {
                 if (a[mid + 1] != val)
                    return mid + 1;           
             }
             if (a[mid] <= val)
             {                 
                 lo = mid + 1;                
             }      
             else
             {
                 hi = mid - 1;
             }
         }
         return - 1;
    }
    if (type == 1)
    {
         while (lo < hi)
         {
             mid = lo + (hi - lo)/2;
             if (a[mid] <= val)
             {
                 if (a[mid + 1] > val)
                    return mid + 1;           
             }
             if (a[mid] <= val)
             {                 
                 lo = mid + 1;                
             }      
             else
             {
                 hi = mid - 1;
             }
         }   
    }
    if (type == 2)
    {
         while (lo < hi)
         {
             mid = lo + (hi - lo)/2;
             if (a[mid] >= val)
             {
                 if (a[mid - 1] < val)
                    return mid + 1;           
             }
             if (a[mid] < val)
             {                 
                 lo = mid - 1;                
             }      
             else
             {
                 hi = mid + 1;
             }
         }     
    }
}

int main()
{
    fin = fopen("cautbin.in", "r");
    fout = fopen("cautbin.out", "w");
    fscanf(fin, "%d", &n);    
    for (int i = 0; i < n; i++)
    {
        fscanf(fin, "%d", &a[i]);        
    }
    fscanf(fin, "%d", &m);
    for (int i = 0; i < m; i++)
    {
        fscanf(fin, "%d%d", &tip, &numar);
        fprintf(fout, "%d\n", Cauta(tip, numar));
    }
    fclose(fin);          
    fclose(fout);
    return 0;
}