#include <iostream>
#include <cstdio>
using namespace std;
const int N = 5e5 + 5;

struct Node{
    int lMaxv, rMaxv, maxv, sum; 
}tree[N << 2];

void bulidTree(int node, int lef, int rig)
{
    if (lef == rig)
    {
        scanf("%d", &tree[node].sum);
        tree[node].lMaxv = tree[node].rMaxv = tree[node].maxv = tree[node].sum;
    }
    else
    {
        int leftNode = node << 1;
        int rightNode = node << 1 | 1;
        int midst = (lef + rig) >> 1;
        bulidTree(leftNode, lef, midst);
        bulidTree(rightNode, midst+1, rig);

        tree[node].sum = tree[leftNode].sum + tree[rightNode].sum;
        tree[node].maxv = max(tree[leftNode].rMaxv + tree[rightNode].lMaxv, max(tree[leftNode].maxv, tree[rightNode].maxv));
        tree[node].lMaxv = max(tree[leftNode].sum + tree[rightNode].lMaxv, tree[leftNode].lMaxv);
        tree[node].rMaxv = max(tree[rightNode].sum + tree[leftNode].rMaxv, tree[rightNode].rMaxv);
    }
}

void modify(int node, int lef, int rig, int x, int c)
{
    if (lef == rig)
    {
        tree[node].lMaxv = tree[node].rMaxv = tree[node].maxv = tree[node].sum = c;
    }
    else
    {
        int leftNode = node << 1;
        int rightNode = node << 1 | 1;
        int midst = (lef + rig) >> 1;
        if (x <= midst) modify(leftNode, lef, midst, x, c);
        else modify(rightNode, midst+1, rig, x, c);

        tree[node].sum = tree[leftNode].sum + tree[rightNode].sum;
        tree[node].maxv = max(tree[leftNode].rMaxv + tree[rightNode].lMaxv, max(tree[leftNode].maxv, tree[rightNode].maxv));
        tree[node].lMaxv = max(tree[leftNode].sum + tree[rightNode].lMaxv, tree[leftNode].lMaxv);
        tree[node].rMaxv = max(tree[rightNode].sum + tree[leftNode].rMaxv, tree[rightNode].rMaxv);
    }
}

Node query(int node, int lef, int rig, int L, int R)
{
    if (L <= lef && rig <= R) return tree[node];
    int leftNode = node << 1;
    int rightNode = node << 1 | 1;
    int midst = (lef + rig) >> 1;
    if (R <= midst) return query(leftNode, lef, midst, L, R);
    if (L > midst) return query(rightNode, midst+1, rig, L, R);

    Node lTemp = query(leftNode, lef, midst, L, R);
    Node rTemp = query(rightNode, midst+1, rig, L, R);
    Node res;
    res.sum = lTemp.sum + rTemp.sum;
    res.maxv = max(lTemp.rMaxv + rTemp.lMaxv, max(lTemp.maxv, rTemp.maxv));
    res.lMaxv = max(lTemp.lMaxv, lTemp.sum + rTemp.lMaxv);
    res.rMaxv = max(rTemp.rMaxv, rTemp.sum + lTemp.rMaxv);
    return res;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    bulidTree(1, 1, n);
    while (m--)
    {
        int op, x, y;
        scanf("%d %d %d", &op, &x, &y);
        if (op == 1) 
        {
            if (x > y) swap(x, y);
            printf("%d\n", query(1, 1, n, x, y).maxv);
        }
        else modify(1, 1, n, x, y);
    }
    return 0;   
}