#include <bits/stdc++.h>
#define int long long int
#define double long double
#define cin fin
#define cout fout
using namespace std;
ifstream fin("arbint.in");
ofstream fout("arbint.out");
template <class T>
class arbint
{
vector<T> lazy;
vector<T> tree;
const int NMAX;
T getmax( const T& val1, const T& val2)
{
if( val1>val2)
return val1;
return val2;
}
public:
arbint(int value): NMAX(4*value+9)
{
lazy.resize(NMAX);
tree.resize(NMAX);
}
void updateRangeUtil(int si, int ss, int se, int us,
int ue, const T& diff)
{
if (lazy[si] != 0)
{
tree[si] += lazy[si];
if (ss != se)
{
lazy[si * 2 ] += lazy[si];
lazy[si * 2 + 1] += lazy[si];
}
lazy[si] = 0;
}
if (ss > se || ss > ue || se < us)
return;
if (ss >= us && se <= ue)
{
tree[si] += diff;
if (ss != se)
{
lazy[si * 2 ] += diff;
lazy[si * 2 + 1] += diff;
}
return;
}
int mid = (ss + se) / 2;
updateRangeUtil(si * 2 , ss, mid, us, ue, diff);
updateRangeUtil(si * 2 + 1, mid + 1, se, us, ue, diff);
tree[si] = getmax(tree[si * 2 ] , tree[si * 2 + 1]);
}
void updateRange(int n, int us, int ue, const T& diff)
{
updateRangeUtil(1, 1, n , us, ue, diff);
}
T getMaxUtil(int ss, int se, int qs, int qe, int si)
{
if (lazy[si] != 0)
{
tree[si] += lazy[si];
if (ss != se)
{
lazy[si * 2 ] += lazy[si];
lazy[si * 2 + 1] += lazy[si];
}
lazy[si] = 0;
}
if (ss > se || ss > qe || se < qs)
return 0;
if (ss >= qs && se <= qe)
return tree[si];
int mid = (ss + se) / 2;
return getmax( getMaxUtil(ss, mid, qs, qe, 2 * si ) ,
getMaxUtil(mid + 1, se, qs, qe, 2 * si + 1) );
}
T getMax(int n, int qs, int qe)
{
if (qs < 1 || qe > n || qs > qe)
{
printf("Invalid Input");
return -1;
}
return getMaxUtil(1, n , qs, qe, 1);
}
void constructSTUtil(const vector<T>& arr, int ss, int se, int si)
{
if (ss > se)
return;
if (ss == se)
{
tree[si] = arr[ss];
return;
}
int mid = (ss + se) / 2;
constructSTUtil(arr, ss, mid, si * 2 );
constructSTUtil(arr, mid + 1, se, si * 2 + 1);
tree[si] = getmax( tree[si * 2 ] , tree[si * 2 + 1]);
}
void constructST(const vector<T>& arr, int n)
{
constructSTUtil(arr, 1, n , 1);
}
/*usage
vector<int>sol;
sol.push_back(0);
sol.push_back(numere);
arbint<int>a(sol.size()-1 + LAMBDA);
a.constructST(sol,sol.size()-1);
a.getMax(sol.size()-1,st,dr);
a.updateRange(sol.size()-1,st,dr, add);
*/
};
int32_t main()
{
int n,m,i;
vector<int>sol={0};
cin>>n>>m;
for(i=1;i<=n;i++)
{
int x;
cin>>x;
sol.push_back(x);
}
arbint<int>a(sol.size());
a.constructST(sol,sol.size()-1);
for(i=1;i<=m;i++)
{
int c,x,y;
cin>>c>>x>>y;
if(c==0)
{
cout<<a.getMax(sol.size()-1,x,y)<<'\n';
}
else
{
int diff;
int value= a.getMax(sol.size()-1,x,x);
diff=value-y;
a.updateRange(sol.size()-1,x,x,-diff);
}
}
return 0;
}