#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#define maximum(a,b) \
({ \
typeof(a) _a = a; \
typeof(b) _b = b; \
_a>=_b?_a:_b; \
})
using namespace std;
class SegmentTree
{
public:
SegmentTree()
{}
SegmentTree(const unsigned int size) :
tree(4*size+66,-1)
{}
void updateValue
(
const int nodeIndex,
const int pos,
const int val,
int left,
int right
)
{
if (left == right)
{
tree[nodeIndex] = val;
}
else
{
const int div = (left+right)/2;
if (pos <= div)
updateValue((nodeIndex<<1)+1, pos, val, left, div);
else
updateValue((nodeIndex+1)<<1, pos, val, div+1, right);
tree[nodeIndex] =
maximum(tree[(nodeIndex<<1)+1], tree[(nodeIndex+1)<<1]);
}
}
void doQuery
(
const int nodeIndex,
const int left,
const int right
) const
{
if (start <= left && right <= end)
{
if (maxi < tree[nodeIndex])
{
maxi = tree[nodeIndex];
indexOfMax = nodeIndex;
}
}
else
{
const int div = (left+right)/2;
if ( start <= div )
{
doQuery((nodeIndex<<1)+1, left, div);
}
if (div < end)
{
doQuery((nodeIndex+1)<<1, div+1, right);
}
}
}
const int queryInterval
(
const int nodeIndex,
const int st,
const int e,
const int left,
const int right
) const
{
maxi = -1;
start = st;
end = e;
doQuery(nodeIndex, left, right);
return maxi;
}
void printTree() const
{
for (unsigned int i=0; i<tree.size(); ++i)
{
cout << tree[i] << " ";
}
cout << "\n";
}
private:
mutable int maxi;
mutable int indexOfMax;
mutable int start;
mutable int end;
vector<int> tree;
};
int main()
{
int n,m;
fstream fin("arbint.in", fstream::in);
fstream fout("arbint.out", fstream::out);
fin >> n >> m;
//cout << n << " " << m << endl;
SegmentTree segTree(n);
for (int i=0; i<n; ++i)
{
int x;
fin >> x;
//cout << "Read " << x << " for position " << i << endl;
segTree.updateValue(0,i,x,0,n-1);
//segTree.printTree();
//cout << endl;
}
for (int i=0; i<m; ++i)
{
int op, a, b;
fin >> op >> a >> b;
switch (op)
{
case 0:
{
//cout << op << " " << a-1 << " " << b-1 << "\n";
fout << segTree.queryInterval(0, a-1, b-1, 0, n-1) << "\n";
}; break;
case 1:
{
//cout << op << " " << a-1 << " " << b << "\n";
segTree.updateValue(0,a-1,b,0,n-1);
//segTree.printTree();
}; break;
}
//cout << "\n";
}
fin.close();
fout.close();
return 0;
}