#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct S { i64 a, b; };
int n, q;
vector<i64> arr;
vector<S> seg;
void b(int i, int l, int r) {
    if(l == r) { seg[i] = {arr[l], arr[l]}; return; }
    int len = r - l + 1, ls = len / 2, m = l + ls - 1;
    if(!ls) m = l;
    b(i*2, l, m); b(i*2+1, m+1, r);
    seg[i] = { min(seg[i*2].b, seg[i*2+1].b), max(seg[i*2].a, seg[i*2+1].a) };
}
void u(int i, int l, int r, int pos, i64 v) {
    if(l == r) { seg[i] = {v, v}; return; }
    int len = r - l + 1, ls = len / 2, m = l + ls - 1;
    if(!ls) m = l;
    if(pos <= m) u(i*2, l, m, pos, v); else u(i*2+1, m+1, r, pos, v);
    seg[i] = { min(seg[i*2].b, seg[i*2+1].b), max(seg[i*2].a, seg[i*2+1].a) };
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    arr.resize(n+1);
    for(int i=1; i<=n; i++) cin >> arr[i];
    seg.resize(4*(n+1));
    b(1, 1, n);
    while(q--){
        int i, p;
        i64 v;
        cin >> i >> v >> p;
        u(1, 1, n, i, v);
        cout << (p ? seg[1].b : seg[1].a) << "\n";
    }
}