#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define down '\n'
#define lli long long int
#define ulli unsigned long long int
#define ld long double
using namespace std;
using namespace __gnu_pbds;
struct node
{
    int first_val,second_val;
    node() { first_val = second_val = INT_MIN; }

};
const int maxn = 1e6+100;
const node EMPTY;

int n,q,a[maxn];
node sg[maxn*4];
void build_tree( int id , int left , int right )
{
    if( left == right )
    {
        sg[id].first_val = a[left];
        return;
    }
    int mid = ( left + right )/2, leftt =  id*2, rightt = id*2+1;
    build_tree(leftt,left,mid);
    build_tree(rightt,mid+1,right);
    sg[id].first_val  = max( sg[leftt].first_val , sg[rightt].first_val );
    sg[id].second_val = max( min( sg[leftt].first_val , sg[rightt].first_val) , max( sg[leftt].second_val , sg[rightt].second_val ) );
}
void update_tree( int id , int left , int right , int pos , int val )
{
    if( right < pos || left > pos )return;
    if( left == right )
    {
        sg[id].first_val = val;
        return;
    }
    int mid = ( left + right )/2, leftt =  id*2, rightt = id*2+1;
    update_tree(leftt,left,mid,pos,val);
    update_tree(rightt,mid+1,right,pos,val);
    sg[id].first_val  = max( sg[leftt].first_val , sg[rightt].first_val );
    sg[id].second_val = max( min( sg[leftt].first_val , sg[rightt].first_val) , max( sg[leftt].second_val , sg[rightt].second_val ) );
}
node query_tree( int id , int left , int right, int u , int v )
{
    if( left > v || right < u ) return EMPTY;
    if( left >= u && right <= v )return sg[id];

    int mid = ( left + right )/2;
    node leftt  =  query_tree(id*2,left,mid,u,v);
    node rightt =  query_tree(id*2+1,mid+1,right,u,v);
    node ans;
    ans.first_val  = max( leftt.first_val , rightt.first_val );
    ans.second_val = max( min( leftt.first_val , rightt.first_val) , max( leftt.second_val , rightt.second_val ) );
    return ans;
}
void read()
{
	cin >> n >> q;
	for( int i =1 ; i <= n; i ++ ) cin >> a[i];
	build_tree(1,1,n);
}
void solve()
{
    int type, left, right, pos, val;
    while( q -- )
    {
        cin >> type;
        if( type == 1 )
        {
            cin >> pos >> val;
            update_tree(1,1,n,pos,val);
        }
        else
        {
            cin >> left >> right;
            node ans = query_tree(1,1,n,left,right);
            cout << ( ans.first_val + ans.second_val)  << " ";
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    solve();
    return 0;
}