#include <bits/stdc++.h>

using namespace std;

class Aint
{
public:
    vector <int> Sum;
    vector <int> Max;
    vector <int> Lazy;
    void Start2 (int n)
    {
        Start(n);
    }
    void Update2 (int nod, int st, int dr, int val, int poz)
    {
        Update(nod, st, dr, val, poz);
    }
    void Range_Update2 (int nod, int st, int dr, int a, int b, int val)
    {
        Range_Update(nod, st, dr, a, b, val);
    }
    int Query_pe_poz2(int nod, int st, int dr, int poz)
    {
        return Query_pe_poz(nod, st, dr, poz);
    }
    int Range_Query2(int nod, int st, int dr, int a, int b)
    {
        return Range_Query(nod, st, dr, a, b);
    }
    int Range_Query_Maxim2 (int nod, int st, int dr, int a, int b)
    {
        return Range_Query_Maxim(nod, st, dr, a, b);
    }
private:
    void Start (int n)
    {
        Sum.resize(n<<2);
        Max.resize(n<<2);
        Lazy.resize (n<<2);
        fill (Sum.begin(), Sum.end(), 0);
        fill (Lazy.begin(), Lazy.end(), 0);
        fill (Max.begin(), Max.end(), 0);
    }
    void Propagation (int nod, int st, int dr)
    {
        if (Lazy[nod] == 0) return;
        if (st == dr)
        {
            Sum[nod]+=Lazy[nod];
            Max[nod]+=Lazy[nod];
            Lazy[nod] = 0;
            return;
        }
        Sum[nod]+=Lazy[nod]*(dr-st+1);
        Max[nod]+=Lazy[nod];
        Lazy[nod<<1] += Lazy[nod];
        Lazy[nod<<1|1]+=Lazy[nod];
        Lazy[nod] = 0;
    }
    void Update (int nod, int st, int dr, int val, int poz)
    {
       // Propagation(nod, st, dr);
        if (st == dr)
        {
            //Sum[poz]+=val;
            Max[nod] = val;
            return;
        }
        int mij = st+dr>>1;
       // Propagation(nod<<1, st, mij);
       // Propagation(nod<<1|1, mij+1, dr);
        if (poz <= mij) Update(nod<<1, st, mij, val, poz);
        else Update(nod<<1|1, mij+1, dr, val, poz);
        //Sum[nod] = Sum[nod<<1]+Sum[nod<<1|1];
        Max[nod] = max(Max[nod<<1],Max[nod<<1|1]);
    }
    int Query_pe_poz (int nod, int st, int dr, int poz)
    {
        Propagation(nod, st, dr);
        if (st == dr)
            return Sum[poz];
        int mij = st+dr>>1;
        Propagation(nod<<1, st, mij);
        Propagation(nod<<1|1, mij+1, dr);
        if (poz <= mij) return Query_pe_poz(nod<<1, st, mij, poz);
        else return Query_pe_poz(nod<<1|1, mij+1, dr, poz);
    }
    int Range_Query (int nod, int st, int dr, int a, int b)
    {
        Propagation(nod, st, dr);
        if (a<=st && dr<=b)
            return Sum[nod];
        int mij = st+dr>>1;
        int Left_sum = 0, Right_sum = 0;
        if (a<=mij) Left_sum = Range_Query(nod<<1, st, mij, a, b);
        if (mij<b) Right_sum = Range_Query(nod<<1|1, mij+1, dr, a, b);
        return Left_sum+Right_sum;
    }
    int Range_Query_Maxim (int nod, int st, int dr, int a, int b)
    {
       // Propagation(nod, st, dr);
        if (a<=st && dr<=b)
            return Max[nod];
        int mij = st+dr>>1;
        int Left_max = 0, Right_max = 0;
        if (a<=mij) Left_max = Range_Query_Maxim(nod<<1, st, mij, a, b);
        if (mij<b) Right_max = Range_Query_Maxim(nod<<1|1, mij+1, dr, a, b);
        return max(Right_max, Left_max);
    }
    void Range_Update (int nod, int st, int dr, int a, int b, int val)
    {
        if (a<=st && dr<=b)
        {
            Lazy[nod] += val;
            return;
        }
        int mij = st+dr>>1;
        Sum[nod] += val*(min(dr, b) - max(a, st)+1);
        if (a<=mij) Range_Update(nod<<1, st, mij, a, b, val);
        if (mij<b) Range_Update(nod<<1|1, mij+1, dr, a, b, val);
    }
} Arbore;
int main()
{
    ifstream fin ("arbint.in");
    ofstream fout ("arbint.out");
    int n, m;
    fin >> n >> m;
    Arbore.Start2(n);
    for (int i = 1; i<=n; ++i)
    {
        int x;
        fin >> x;
        Arbore.Update2(1, 1, n, x, i);
    }
    for (int i = 1; i<=m; ++i)
    {
        int x, a, b;
        fin >> x >> a >>  b;
        if (x)
        {
            Arbore.Update2(1, 1, n, b, a);
        }
        else
        {
            fout << Arbore.Range_Query_Maxim2(1, 1, n, a, b) << '\n';
        }
    }
    return 0;
}