#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 500010;

int w[N], n, m;

struct node 
{
    int l, r;
    int sum, lmax, rmax, tmax; // 区间总和，前缀和，后缀和，最大连续字段和 
}tr[N * 4];

void push_up(node &u, node &l, node &r) 
{
    u.sum = l.sum + r.sum; // 区间总和就是左区间和+右区间和
    u.lmax = max(l.lmax, l.sum + r.lmax); // 做前缀和为，左面区间的前缀和或左区间总和+右区间的前缀和（取最值）
    u.rmax = max(r.rmax, r.sum + l.rmax); // 同上
    u.tmax = max({l.tmax, r.tmax, l.rmax + r.lmax}); // 总区间的最大连续子段和就是，左区间的最大子段和，右区间的最大子段和，左区间的后缀和+右区间的前缀和（取最大值）
}

void push_up(int u) // 更新：利用子节点更新父节点
{
    push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) // 建树
{
    if (l == r) // 递归到根节点 直接赋值
        tr[u] = {l, r, w[r], w[r], w[r], w[r]};
    else
    {
        tr[u] = {l, r}; // 一定要给区间赋值，否则会段错误
        int mid = l + r >> 1;
        build(u << 1, l, mid); // 递归左子树
        build(u << 1 | 1, mid + 1, r); // 递归右子树
        push_up(u); // 记得更新
    }
}

void modity(int u, int x, int v) // 修改
{
    if (tr[u].l == x && tr[u].r == x) // 如果递归到了要修改的那个点 直接修改
        tr[u] = {x, x, v, v, v, v};
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            modity(u << 1, x, v); // 如果在左面就递归左子树
        if (x > mid)
            modity(u << 1 | 1, x, v); // 否则递归右子树
        push_up(u); // 记得更新
    }
}

node query(int u, int l, int r) // 查询
{
    if (tr[u].l >= l && tr[u].r <= r) // 如果这段区间被覆盖，那么直接返回这段区间的最大值
        return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;

        if (r <= mid) // 如果区间在左边，就去递归左子树
            return query(u << 1, l, r);
        else if (l > mid) // 否则递归右子树
            return query(u << 1 | 1, l, r);
        else // 如果都有的话
        {
            auto left = query(u << 1, l, mid); // 找到左边的最值
            auto right = query(u << 1 | 1, mid + 1, r); // 找到右边的最值
            node res;
            push_up(res, left, right); // 求得最大值，返回
            return res;
        }

    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);

    build(1, 1, n);

    while (m --)
    {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);

        if (k == 1)
        {
            if (x > y)
                swap(x, y);
            printf("%d\n", query(1, x, y).tmax);
        }
        else
        {
            modity(1, x, y);
        }
    }

    return 0;
}