#include <bits/stdc++.h>

namespace MyLib
{
	template<typename T, class Picker, T default_value> class LiteralSegmentTree
	{
	protected:
		std::vector<std::vector<T>> containers;
	
	public:
		constexpr LiteralSegmentTree(const std::vector<T>& initializer)
		{
			containers.clear();
	
			if (initializer.size() == 0) [[unlikely]] return;
			else if (initializer.size() == 1) [[unlikely]] { containers.emplace_back(1, initializer[0]); return; }
	
			uint_fast32_t l = 0, r = 30;
			while (l + 1 < r)
			{
				const auto c = (l + r) >> 1;
				if (((uint_fast32_t)1 << c) < initializer.size())
					l = c;
				else
					r = c;
			}
	
			containers.emplace_back((uint_fast32_t)1 << r);
	
			uint_fast32_t i;
			for (i = 0; i != initializer.size(); ++i)
				containers[0][i] = initializer[i];
			for (; i != ((uint_fast32_t)1 << r); ++i)
				containers[0][i] = default_value;
	
			for (--r; r != 0; --r)
			{
				containers.emplace_back((uint_fast32_t)1 << r);
				[[assume(containers.size() >= 2)]];
				for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
					containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
			}
			containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
		}
	
		constexpr LiteralSegmentTree(std::vector<T>&& initializer)
		{
			containers.clear();
	
			if (initializer.size() == 0) [[unlikely]] return;
	
			uint_fast32_t l = 0, r = 30;
			while (l + 1 < r)
			{
				const auto c = (l + r) >> 1;
				if (((uint_fast32_t)1 << c) < initializer.size())
					l = c;
				else
					r = c;
			}
	
			containers.emplace_back(std::move(initializer));
			containers[0].resize((uint_fast32_t)1 << r, default_value);
	
			uint_fast32_t i;
			for (--r; r != 0; --r)
			{
				containers.emplace_back((uint_fast32_t)1 << r);
				[[assume(containers.size() >= 2)]];
				for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
					containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
			}
			containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
		}
	
		constexpr LiteralSegmentTree(const uint_fast32_t n) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, default_value)) { }
		constexpr LiteralSegmentTree(const uint_fast32_t n, const T initial_value) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, initial_value)) { }
	
		[[nodiscard]] constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; }
	
		[[nodiscard]] constexpr uint_fast32_t size() const noexcept { return containers[0].size(); }
		[[nodiscard]] constexpr uint_fast32_t layer() const noexcept { return containers.size(); }
	
		constexpr T update(uint_fast32_t index, const T value) noexcept
		{
			containers[0][index] = value;
	
			index >>= 1;
			for (uint_fast32_t i = 1; i != containers.size(); ++i, index >>= 1)
				containers[i][index] = Picker()(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]);
	
			return value;
		}
	
		[[nodiscard]] constexpr T range_pick_up(uint_fast32_t first_index, uint_fast32_t end_index) const noexcept
		{
			if (containers.size() == 0 || end_index > containers[0].size()) [[unlikely]] return default_value;
	
			T ret_l = default_value, ret_r = default_value;
			for (uint_fast32_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer)
			{
				if (first_index & 1)
					ret_l = Picker()(ret_l, containers[cur_layer][first_index]), ++first_index;
				if (end_index & 1)
					ret_r = Picker()(containers[cur_layer][end_index - 1], ret_r);
			}
	
			return Picker()(ret_l, ret_r);
		}
	};

	template<typename T> using DefaultMaxPicker = decltype([](const T a, const T b) { return std::max<T>(a, b); });
	
	template<typename T, class MaxPicker, T default_value = std::numeric_limits<T>::lowest()>
	class MaxSegmentTree : public LiteralSegmentTree<T, MaxPicker, default_value>
	{
	public:
		constexpr MaxSegmentTree(const std::vector<T>& initializer) : LiteralSegmentTree<T, MaxPicker, default_value>(initializer) { }
		constexpr MaxSegmentTree(std::vector<T>&& initializer) : LiteralSegmentTree<T, MaxPicker, default_value>(std::move(initializer)) { }
		template<typename... Args> constexpr MaxSegmentTree(const Args... args) : LiteralSegmentTree<T, MaxPicker, default_value>(std::forward<Args>(args)...) { }
	
		[[nodiscard]] constexpr uint_fast32_t leftest_above(const uint_fast32_t first, const uint_fast32_t last, const T limit) const noexcept
		{
			[[assume(first <= last)]];
			if (this->containers.size() == 0) [[unlikely]] return 0;
	
			uint_fast32_t cur_layer, cur_index;
	
			uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
			uint_fast32_t first_temp = first, last_temp = last;
			for (cur_layer = 0; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
			{
				if (first_temp & 1)
				{
					if (this->containers[cur_layer][first_temp] >= limit)
						break;
					++first_temp;
				}
				if (last_temp & 1)
				{
					[[assume(last_temp >= 1)]];
					if (this->containers[cur_layer][last_temp - 1] >= limit)
						candidate_layer = cur_layer, candidate_index = last_temp - 1;
					//--last_temp;
				}
			}
	
			if (first_temp != last_temp) cur_index = first_temp;
			else if (candidate_layer == this->containers.size()) return this->containers[0].size();
			else cur_layer = candidate_layer, cur_index = candidate_index;
	
			while (cur_layer != 0)
			{
				--cur_layer, cur_index <<= 1;
				if (this->containers[cur_layer][cur_index] < limit)
					cur_index |= 1;
			}
	
			return cur_index;
		}
	
		[[nodiscard]] constexpr uint_fast32_t rightest_above(const uint_fast32_t first, const uint_fast32_t last, const T limit) const noexcept
		{
			[[assume(first <= last)]];
			if (this->containers.size() == 0) [[unlikely]] return 0;
	
			uint_fast32_t cur_layer, cur_index;
	
			uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
			uint_fast32_t first_temp = first, last_temp = last;
			for (cur_layer = 0; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
			{
				if (last_temp & 1)
				{
					[[assume(last_temp >= 1)]];
					if (this->containers[cur_layer][last_temp - 1] >= limit)
						break;
					//--last_temp;
				}
				if (first_temp & 1)
				{
					if (this->containers[cur_layer][first_temp] >= limit)
						candidate_layer = cur_layer, candidate_index = first_temp;
					++first_temp;
				}
			}
	
			if (first_temp != last_temp) cur_index = last_temp - 1;
			else if (candidate_layer == this->containers.size()) return this->containers[0].size();
			else cur_layer = candidate_layer, cur_index = candidate_index;
	
			while (cur_layer != 0)
			{
				--cur_layer, cur_index <<= 1;
				if (this->containers[cur_layer][cur_index | 1] >= limit)
					cur_index |= 1;
			}
	
			return cur_index;
		}
	};
}

[[nodiscard]] static inline constexpr std::vector<int_least32_t> solve(const uint_fast32_t N, const uint_fast32_t Q, std::vector<uint_least32_t>&& A, const std::vector<std::pair<char, uint_least32_t>>& queries) noexcept
{
	MyLib::MaxSegmentTree<uint_least32_t, MyLib::DefaultMaxPicker<uint_least32_t>> cyans(std::move(A));
	std::vector<int_least32_t> ans;
	ans.reserve(Q);

	for (const auto& [c, x] : queries)
	{
		if (c == '1')
		{
			const uint_fast32_t pos = cyans.leftest_above(0, N, x + 1);
			if (pos >= N) ans.push_back(-1);
			else ans.push_back(pos + 1), cyans.update(pos, 0);
		}
		else
		{
			const uint_fast32_t pos = cyans.rightest_above(0, N, x + 1);
			if (pos >= N) ans.push_back(-1);
			else ans.push_back(pos + 1), cyans.update(pos, 0);
		}
	}

	return ans;
}

static inline void output(const std::vector<int_least32_t>& ans) noexcept
{
	for (const auto& res : ans)
		std::cout << res << '\n';
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	uint_fast32_t N, Q;
	std::cin >> N >> Q;
	std::vector<uint_least32_t> A(N);
	std::vector<std::pair<char, uint_least32_t>> queries(Q);
	for (auto& a : A) std::cin >> a;
	for (auto& [c, x] : queries) std::cin >> c >> x;

	output(solve(N, Q, std::move(A), queries));
	return 0;
}