#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, a[100000], mid;

int r0(int x)
{
    int li, ls;
    li = 0; ls = n-1;
    while(li<ls){
        mid = (li+ls)/2;
        if(a[mid]<x){
            li = mid+1;
        }
        else if(a[mid]>x){
            ls = mid-1;
        }
        else{
            if(a[mid+1] == x)
                li=mid+1;
            else{
                li = 2*mid - ls;
                break;
            }
        }
    }
    mid = (li+ls)/2;
    if(a[mid] == x)
        return mid;
    else
        return -2;

}

int r1(int x)
{
    int li, ls;
    li = 0; ls = n-1;
    while(li<ls){
        mid = (li+ls)/2;
        if(a[mid]<x){
            li = mid+1;
        }
        else if(a[mid]>x){
            ls = mid-1;
        }
        else{
            if(a[mid+1] == x)
                li=mid+1;
            else{
                li = 2*mid - ls;
                break;
            }
        }
    }
    mid = (li+ls)/2;
    return mid;
}

int r2(int x)
{
    int li, ls;
    li = 0; ls = n-1;
    while(li<ls){
        mid = (li+ls)/2;
        if(a[mid]<x){
            li = mid+1;
        }
        else if(a[mid]>x){
            ls = mid-1;
        }
        else{
            if(a[mid-1] == x)
                ls=mid-1;
            else{
                li = 2*mid - ls;
                break;
            }
        }
    }
    mid = (li+ls)/2;
    return mid;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int t, x, sol;
    scanf("%d%c", &n);
    for(int i=0; i<n; i++)
        scanf("%d ", &a[i]);
    scanf("%d%c", &m);
    for(int i=0; i<m; i++){
        sol = 0;
        scanf("%d %d\n", &t, &x);
        if(t==0)
           sol = r0(x);
        else if(t==1)
           sol = r1(x);
        else if(t==2)
           sol = r2(x);
        printf("%d\n", sol+1);
    }
    return 0;
}