#include<bits/stdc++.h>
using namespace std;
#define ll long long


const int N=200005;
int a[N];
pair<int,int>sg[4*N];


void build(int node, int start, int ed){
    if(start == ed){
        sg[node] = {a[start],a[start]};
        return;
    }

    int mid= (start + ed-1)/2;

    build(node*2 , start, mid);
    build(node*2 +1, mid+1, ed);
    sg[node].first= min(sg[node*2].second , sg[node*2 +1].second);
    sg[node].second = max(sg[node*2].first , sg[node*2 +1].first);
}

void update(int node, int start, int ed , int idx, int val){
    if(start == ed){
        sg[node]= {val, val};
        return;
    }

    int mid= (start + ed-1)/2;

    if(idx <= mid){
        update(node*2 , start, mid , idx, val);
    }
    else update(node*2 +1, mid+1, ed , idx, val);
    sg[node].first= min(sg[node*2].second , sg[node*2 +1].second);
    sg[node].second = max(sg[node*2].first , sg[node*2 +1].first);

}

int main(){
    int n,q;
    cin >> n >> q;

    //vector<int>a(n+1);
    for(int i=1; i<=n; i++)cin >> a[i];

    build(1,1,n);

    while(q--){
        int i, v, p;
        cin >> i >> v >> p;

        update(1, 1, n, i, v);

        if(p == 0)cout << sg[1].first <<endl;
        else cout << sg[1].second <<endl;
    }
}