#include <bits/stdc++.h>

using namespace std;

int generateRandomNumber() {
	return abs((1LL * rand() << 15) + rand()) % 1000000000 + 1; // 1 ... 1e9
}

struct TreapNode {
	int position, value, priority;
	TreapNode *left, *right;

	int minPosition, maxPosition, maxValue;

	TreapNode(TreapNode *l, TreapNode *r, int pos, int val, int pr, int minPos, int maxPos) {
		left = l;
		right = r;
		position = pos;
		value = val;
		priority = pr;
		minPosition = minPos;
		maxPosition = maxPos;
		maxValue = value;
	}
};
TreapNode *NILL = new TreapNode(nullptr, nullptr, -1, -1e9, -1, 1e9, -1e9);

void leftRotate(TreapNode *& node) {
	TreapNode *aux = node->right;
	node->right = aux->left;
	aux->left = node;
	node = aux;
}

void rightRotate(TreapNode *& node) {
	TreapNode *aux = node->left;
	node->left = aux->right;
	aux->right = node;
	node = aux;
}

void recheck(TreapNode *& node) {
	if (node == NILL) return;
	node->maxValue = node->value;
	node->maxValue = max(node->maxValue, node->left->maxValue);
	node->maxValue = max(node->maxValue, node->right->maxValue);

	node->minPosition = min(node->position, node->left->minPosition);
	node->maxPosition = max(node->position, node->right->maxPosition);
}

void balance(TreapNode *& node) {
	if (node == NILL) return;
	if (node->priority < node->left->priority) {
		rightRotate(node);
	}
	if (node->priority < node->right->priority) {
		leftRotate(node);
	}
	recheck(node->left);
	recheck(node->right);
	recheck(node);
}

void insert(TreapNode *& node, int pos, int val) {
	if (node == NILL) {
		node = new TreapNode(NILL, NILL, pos, val, generateRandomNumber(), pos, pos);
		return;
	}
	if (pos < node->position) {
		insert(node->left, pos, val);
	} else {
		insert(node->right, pos, val);
	}
	balance(node);
}

int maximumQuery(TreapNode *& node, int left, int right) {
	if (node == NILL) return -1e9;

	int maxLeft = -1e9;
	int maxRight = -1e9;
	int maxCurrent = -1e9;

	if (left <= node->minPosition and node->maxPosition <= right) return node->maxValue;

	if (left <= node->position and node->position <= right) maxCurrent = node->value;
	if (left <= node->left->maxPosition) {
		maxLeft = maximumQuery(node->left, left, right);
	}
	if (node->right->minPosition <= right) {
		maxRight = maximumQuery(node->right, left, right);
	}

	return max(maxCurrent, max(maxLeft, maxRight));
}

void erase(TreapNode *& node, int pos) {
	if (node == NILL) return;
	if (pos < node->position) {
		erase(node->left, pos);
	} else if (pos > node->position) {
		erase(node->right, pos);
	} else {
		if (node->left == NILL and node->right == NILL) {
			delete node;
			node = NILL;
		} else if (node->left->position < node->right->position) {
			leftRotate(node);
			erase(node, pos);
		} else {
			rightRotate(node);
			erase(node, pos);
		}
	}
	balance(node);
}

int main(){
	freopen("arbint.in", "r", stdin);
	freopen("arbint.out", "w", stdout);
	srand(6565);
	TreapNode *root = NILL;

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		int val;
		cin >> val;
		insert(root, i, val);
	}
	for (int i = 1; i <= m; ++i) {
		int type, x, y;
		cin >> type >> x >> y;

		if (type == 0) {
			cout << maximumQuery(root, x, y) << '\n';
		} else {
			erase(root, x);
			insert(root, x, y);
		}
	}
	return 0;
}