#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>

/*
	https://medium.com/@Rameshaditya/an-introduction-to-segment-trees-2469c7bb99b4
	Un arbore de intervale este un arbore binar care odata construit ne permite sa raspunde
	la intrebari de forma: da-mi elementul minim din intervalul [2, 10] din vector in O(log n)
	ceea ce este foarte eficient.

	Complexitate:
		a. Build: O(n)
		b. Query: O(log n)
		c. Update: O(log n)

	a. Build:
		- folosim divide et impera, anume: 
			a. O problema elementare este atunci cand subintervalul are doar 1 singur element
			b. Daca nu e o problema elementara atunci impartim intervalul in 2 subintervale si in final
			   combinam rezultatele(in functie de ce ni se cere)

		Un arbore de intervale se stocheaza in acelasi mod ca si un heap, arbore binar: un vector cu 2 * n elemente
		in care fiul stang al nodului de pe pozitia i este pe pozitia 2 * i iar cel drept pe pozitia 2 * i + 1

	b. Query:
		Parcurgem arborele si verificam niste chestii:
			a. Intervalul nodului curent este total in afara intervalului pe care-l cautam => returam o valoare care sa nu ne incurce si nu 
			   mergem mai departe cu recursia(asta este foarte eficient pt arbori mari pt ca sarim peste multe noduri)
		    b. Intervalul nodului curent este partial in intervalul pe care-l cautam caz in care mergem recursiv pe ambii fii ai nodului si combinam rezultatele obtinute
		    c. Intervalul nodului este continut partial in intervalul pe care-l cautam caz in care returnam valoarea din nod:
		    	if(left <= start && end <= right) return tree[idx];

	c. Update:
		La fel ca la query doar ca acum:
			a. Cand avem un subvector cu un singur element atunci inseamna ca am gasit elementul pe care-l cautam si-l actualizam in vector
			b. In rest:
				- tinem cont de indexul elementului pe care-l actualizam pt a determina nodul
				- refacem parintii nodului modificat	  
*/

typedef unsigned int uint;

#define MAX(a, b) ((a < b) ? b : a)

struct segmentTree
{
	uint *tree;
	uint length;
};

void build(uint idx, uint *tree, uint *data, uint start, uint end);
uint query(uint idx, uint *tree, uint start, uint end, uint left, uint right);
void update(uint idx, uint *tree, uint pos, uint val, uint start, uint end);

void init(struct segmentTree *st, uint *data, uint n);

int main(void)
{
	FILE *in =  fopen("arbint.in", "r");
	FILE *out = fopen("arbint.out", "w");

	if(in != NULL && out != NULL)
	{
		uint n, m;
		fscanf(in, "%u%*c%u%*c", &n, &m);
		uint *data = malloc(sizeof(uint) * n);
		uint i = 0;
		for(; i < n; i++)
			fscanf(in, "%u%*c", &data[i]);

		struct segmentTree st;
		init(&st, data, n);

		i = 0;
		for(; i < m; i++)
		{
			uint op, a, b;
			fscanf(in, "%u%*c%u%*c%u%*c", &op, &a, &b);

			if(!op)
				fprintf(out, "%u\n", query(1, st.tree, 0, n - 1, a - 1, b - 1));
			else
				update(1, st.tree, a - 1, b, 0, n - 1);
		}
		
		free(data);
		free(st.tree);
		fclose(in);
		fclose(out);
	}
	else
	{
		printf("file error\n");
	}

	return 0;
}

void init(struct segmentTree *st, uint *data, uint n)
{
	st->length = 4 * n + 2;
	st->tree = malloc(sizeof(uint) * st->length);
	if(st->tree != NULL)
		build(1, st->tree, data, 0, n - 1);
	else
		printf("Failed to allocate memory for tree buffer[%llu bytes]\n", sizeof(uint) * st->length);
}

void update(uint idx, uint *tree, uint pos, uint val, uint start, uint end)
{
	if(start <= end)
	{
		if(start == end)
			tree[idx] = val;
		else
		{
			uint mid = (start + end) / 2;

			if(pos <= mid)
				update(2 * idx, tree, pos, val, start, mid);
			else
				update(2 * idx + 1, tree, pos, val, mid + 1, end);

			tree[idx] = MAX(tree[2 * idx], tree[2 * idx + 1]);
		}
	}
}

uint query(uint idx, uint *tree, uint start, uint end, uint left, uint right)
{
	if(start <= end)
	{
		if(left > end || right < start)
			return 0;
		else 
		{
			if(left <= start && end <= right)
				return tree[idx];
			else
			{
				uint mid = (start + end) / 2;
				uint a = query(2 * idx, tree, start, mid, left, right);
				uint b = query(2 * idx + 1, tree, mid + 1, end, left, right);
				return MAX(a, b);
			}
		}
	}
}

void build(uint idx, uint *tree, uint *data, uint start, uint end)
{
	if(start <= end)
	{
		if(start == end)
		{
			tree[idx] = data[start];
		}
		else
		{
			int mid = (start + end) / 2;
			build(2 * idx, tree, data, start, mid);
			build(2 * idx + 1, tree, data, mid + 1, end);
			tree[idx] = MAX(tree[2 * idx], tree[2 * idx + 1]);
		}
	}
}

uint gcd(uint a, uint b)
{
	while(b)
	{
		uint temp = a;
		a = b;
		b = temp % a;
	}
	return a;
}