//============================================================================
// Name        : cautareBinara.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <fstream>
#include <vector>
#include <utility>

using namespace std;

class Solution
{
	private:
		vector <uint32_t> series;
		uint32_t N, M, x, t;
		ifstream inFile;
		ofstream outFile;
		vector <pair<uint32_t, uint32_t>> questions;

		int findX(uint32_t start, uint32_t stop, uint32_t qType){
			int pos = -1;
			if(start >= stop)
			{
				if(series[start] == x)
					pos = start;
			}
			else
			{
				int middle = (stop + start) / 2;
				if (qType == 2)
				{
					pos = findX(start,middle,qType);
					if(pos == -1)
						pos = findX(middle + 1, stop,qType);
				}else
				{
					//search right first to get the biggest position of x
					pos = findX(middle + 1, stop,qType);
					if(pos == -1)
						pos = findX(start,middle,qType);
				}
			}
			return pos;
		}
	public:
		Solution()
		{
			N=0,M=0,x=0,t=0;
		}

		int readSolutionParameters(string fileName){
			int ret = 0;
			uint32_t i = 0;
			inFile.open (fileName, ifstream::in);
			if(!inFile.eof())
			{
				inFile >> N;
				for(i = 0; i < N; ++i)
				{
					inFile >> x;
					series.push_back(x);
				}
				inFile >> M;
				for(i = 0; i < M; ++i)
				{
					inFile >> t >> x;
					questions.push_back(make_pair(t,x));
				}
				inFile.close();
			}else
			{
				ret = -1;
			}
			return ret;
		}

		void printSolutionParameters(string fileName)
		{
			uint32_t i = 0;
			outFile.open (fileName, ofstream::out);
			outFile << N << endl;
			for(i = 0; i < N; ++i)
			{
				outFile << series[i]<<' ';
			}
			outFile << endl << M << endl;
			for(i = 0; i < M; ++i)
			{
				outFile << questions[i].first << ' ' << questions[i].second << endl;
			}
			outFile << endl;
		}

		void answer(string fileName)
		{
			outFile.open (fileName, ofstream::out);
			uint32_t i = 0;
			int pos = -1, tempPos = -1;
			uint32_t qType = 0;
			for(i = 0; i < M; ++i)
			{
				qType = questions[i].first;
				x = questions[i].second;
				pos = findX(0, series.size() -1,qType);
				if(pos != -1)
				{
					if (qType == 1)
					{
						tempPos = pos - 1;
						if(series[tempPos] != series[pos])
							pos = tempPos;
					}else if (qType ==2)
					{
						tempPos = pos + 1;
						if(series[tempPos] != series[pos])
							pos = tempPos;
					}
				}
				pos ++;
				outFile << pos<<endl;
			}
			outFile.close();
		}

		~Solution()
		{
		}
};
int main() {
	int ret = 0;
	Solution s;
	ret = s.readSolutionParameters("cautbin.in");
	if (ret == -1)
	{
		printf("File error\n");
	}
	//s.printSolutionParameters("cautbin.out");
	s.answer("cautbin.out");
	return ret;
}