#include <iostream>
#include <fstream>

using namespace std;
int n,m;
int a[50001];
int intrebari[50001][2];

int binarySearch0 (int left, int right, int number) {
	if (left <= right) {
		int mid = (left + right)/2;

		if (a[mid] == number) {
			while (mid < n) {
				if (a[mid] == a[mid + 1]) {
					mid++;
				}else {
					return mid;
				}
			}
		}
		if (a[mid] < number) {
			return binarySearch0 (mid, right, number);
		}

		if (a[mid] > number) {
			return binarySearch0 (left, mid, number);
		}
	}else {
		return -1;
	}
}

int binarySearch1 (int left, int right, int number) {
	if (left <= right) {
		int mid = (left + right) / 2; 
		if (a[mid] == number) {
			while (mid < n){
				if (a[mid + 1] == number){
					mid ++;
				}else {
					return mid;
				}
			}
		}
		if (a[mid] < number) {
			return binarySearch1 (mid, right, number);
		}else {
			return mid;
		}

	}else {
		return left;
	}
}

int binarySearch2 (int left, int right, int number) {
	if (left <= right) {
		int mid = (left + right) / 2; 
		if (a[mid] == number) {
			while (mid > 1){
				if (a[mid - 1] == number){
					mid --;
				}else {
					return mid;
				}
			}
		}
		if (a[mid] > number) {
			return binarySearch2 (left, mid, number);
		}else {
			return mid;
		}

	}else {
		return right;
	}
}

int binarySearch (int left, int right, int direction, int number ) {
	switch (direction) {
		case 0 :
		return binarySearch0 (left, right, number);
		case 1 :
		return binarySearch1 (left, right, number);
		case 2 :
		return binarySearch2 (left, right, number);
	} 
	return -1;
}

int main ()
{
	ifstream in ("cautbin.in");
	ofstream out ("cautbin.out");
	in>>n;
	for (int i = 1; i<= n; i++) {
		in>>a[i];
	}
	in>>m;
	for (int i = 0; i < m; i++) {
		in>>intrebari[i][0]>>intrebari[i][1];
	}
	
	for (int i = 0; i< m; i++ ) {
		cout<<binarySearch (1, n, intrebari[i][0], intrebari[i][1])<<"\n";
	}
}