#include <iostream>
#include <fstream>
using namespace std;

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

const int MAX_LENGTH = 100000;

void questionType0(int numbersLength, int numbers[MAX_LENGTH + 1], int xValue) {
    int left = 1, right = numbersLength;
    while (left < right) {
        int middle = (left + right) / 2;
        if (numbers[middle] < xValue) {
            left = middle + 1;
        } else {
            right = middle;
            if (middle + 1 <= numbersLength && numbers[middle + 1] == xValue) {
                left = middle + 1;
                right = numbersLength;
            }
        }
    }
    if (numbers[left] == xValue) {
        fout << left;
    } else {
        fout << -1;
    }
}

void questionType1(int numbersLength, int numbers[MAX_LENGTH + 1], int xValue) {
    int left = 1, right = numbersLength;
    while (left < right) {
        int middle = (left + right) / 2;
        if (numbers[middle] < xValue) {
            left = middle + 1;
        } else {
            right = middle;
            if (middle + 1 <= numbersLength && numbers[middle + 1] == xValue) {
                left = middle + 1;
                right = numbersLength;
            }
        }
    }
    fout << left;
}

void questionType2(int numbersLength, int numbers[MAX_LENGTH + 1], int xValue) {
    int left = 1, right = numbersLength;
    while (left < right) {
        int middle = (left + right) / 2;
        if (numbers[middle] < xValue) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }
    fout << left;
}

int main() {
    int numbersLength;
    fin >> numbersLength;
    int numbers[MAX_LENGTH + 1];
    for (int index = 1; index <= numbersLength; ++index) {
        fin >> numbers[index];
    }
    int numberOfQuestions;
    fin >> numberOfQuestions;
    for (int question = 1; question <= numberOfQuestions; ++question) {
        int questionType, xValue;
        fin >> questionType >> xValue;
        if (questionType == 0) {
            questionType0(numbersLength, numbers, xValue);
        } else if (questionType == 1) {
            questionType1(numbersLength, numbers, xValue);
        } else {
            questionType2(numbersLength, numbers, xValue);
        }
        fout << '\n';
    }
    return 0;
}
/*
 5
 1 3 3 3 5
 3
 0 3
 1 3
 2 3
 =>
 4
 4
 2
 
 4
 5 5 5 5
 1
 1 5
 =>
 4
 
 4
 3 3 3 3
 2
 2 1
 1 5
 =>
 1
 4
 
 9
 1 2 2 3 3 5 6 9 9
 1
 2 2
 =>
 2
 
 9
 1 3 3 3 3 5 6 9 9
 1
 2 2
 =>
 2
 
 5
 1 2 3 4 5
 1
 1 7
 =>
 5
 
 5
 1 2 3 3 5
 1
 1 4
 => 5
 
 3
 1 2 3
 2
 0 5
 0 9
 =>
 -1
 -1
 */