#include <iostream>
#include <fstream>

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

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

		if (a [mid] == number) {
			if (direction == 0 || direction == 1){
				while (mid < n) {
					if (a[mid] == a[mid + 1]) {
						mid++;
					}else {
						return mid;
					}
				}
			}
			if (direction == 2) {
				while (mid > 1) {
					if (a[mid-1] == a[mid]) {
						mid--;
					}else {
						return mid;
					}
				}
			}
		}

		if (a[mid] < number) {
			return binarySearch (mid, right, direction, number);
		}

		if (a[mid] > number) {
			return binarySearch (left, mid, direction, number);
		}

	}else {
		if (direction == 0) {
			return -1;
		} 
		if (direction == 1) {
			while (right < n) {
				if (a[right] == a[right + 1]) {
					right++;
				}else {
					return right;
				}
			}
		}
		if (direction == 2) {
			while (left > 1) {
				if (a[left-1] == a[left]) {
					left--;
				}else {
					return left;
				}
			}
		}
	}
}

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";
	}
}