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

int n,q;
const int MAXN = 2e5 + 5;

struct Node {
    int l, r;
    int min_val, max_val;
    Node *left, *right;

    Node(int l, int r): l(l), r(r), left(nullptr), right(nullptr), min_val(0), max_val(0) {}
};

int A[MAXN];

Node* build(int l, int r) {
    Node* node = new Node(l, r);
    if (l == r) {
        node->min_val = node->max_val = A[l];
        return node;
    }
    int mid = (l + r) / 2;
    node->left = build(l, mid);
    node->right = build(mid + 1, r);
    node->min_val = min(node->left->min_val, node->right->min_val);
    node->max_val = max(node->left->max_val, node->right->max_val);
    return node;
}

void update(Node* node, int idx, int val) {
    if (node->l == node->r) {
        node->min_val = node->max_val = val;
        return;
    }
    if (idx <= node->left->r)
        update(node->left, idx, val);
    else
        update(node->right, idx, val);

    node->min_val = min(node->left->min_val, node->right->min_val);
    node->max_val = max(node->left->max_val, node->right->max_val);
}

int simulate(Node* node, bool thakur_turn) {
    if (node->l == node->r) return A[node->l];
    
    if (thakur_turn) {
        if (node->left->max_val <= node->right->max_val)
            return simulate(node->left, !thakur_turn);
        else
            return simulate(node->right, !thakur_turn);
    } else {
        if (node->left->min_val >= node->right->min_val)
            return simulate(node->left, !thakur_turn);
        else
            return simulate(node->right, !thakur_turn);
    }
}

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> A[i];
    Node* root = build(1, n);
    while(q--) {
        int i,v,p;
        cin >> i >> v >> p;
        update(root, i, v);
        A[i] = v;
        cout << simulate(root, p == 0) << '\n';
    }
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}