#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl '\n'
#define ll long long
#define ld long double
#define vi vector<ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define srt(v) sort(v.begin(),v.end())
#define rep(i, a, b) for(ll i = (a); i < (b); i++)
#define print(v) for(auto e:v) cout<<e<<" "; cout<<endl;
#define printp(v) for(auto e:v) cout<<e.first<<" "<<e.second<<endl;

const int N = 2e5;
ll arr[N];
pair<ll,ll>seg[4*N];
void build(ll node,ll start,ll end){
    if(start == end){
        seg[node] = {arr[start],arr[start]};
        return;
    }
    ll mid = (start+end-1)/2;
    build(node*2,start,mid);
    build(node*2+1,mid+1,end);
    seg[node].first = min(seg[node*2].second,seg[node*2 +1].second);
    seg[node].second = max(seg[node*2].first,seg[node*2 +1].first);
}

void update(ll node,ll start,ll end,ll pos,ll v){
    if(start == end){
        seg[node] = {v,v};
        arr[start] = v;
        return;
    }
    ll mid = (start+end-1)/2;
    if(pos<=mid){
        update(node*2,start,mid,pos,v);
    }
    else{
        update(node*2 +1,mid+1,end,pos,v);
    }
    seg[node].first = min(seg[node*2].second,seg[node*2 +1].second);
    seg[node].second = max(seg[node*2].first,seg[node*2 +1].first);
}

void solve() {
    ll n,m;cin>>n>>m;
    //vi p(n);
    rep(i,1,n+1){
        cin>>arr[i];
    }
    build(1,1,n);
    while (m--)
    {
        ll i,v,p;cin>>i>>v>>p;
        update(1,1,n,i,v);
        if(p==0){
            cout<<seg[1].first<<endl;
        }
        else{
            cout<<seg[1].second<<endl;
        }
    }
    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;//cin>>t;
    for(int i =1;i<=t;i++){
        solve();
    }
    return 0;
}