本题没有可用的提交语言。

题目背景

The English statement is provided here. You must submit your solution only in the Chinese version.

题目描述

在 DerrickLo 的游戏中，他有 $n$ 个属性，第 $i$ 个属性的初始值为 $a_i$，接下来根据游戏进度变化，他会给你一些修改操作或者询问，形如：

• 1 k x，将 $a_k$ 变为 $x$（修改操作）。
• 2 l r，问仅通过以下操作（但不真正执行）使区间变为相同的数的最小代价（询问）。操作分别是：

1. 选择整数 $p$，将 $a_p$ 增加 $1$，代价为 $1$。
2. 选择整数区间 $x,y$，将 $a_x\dots a_y$ 全部变为 $\max\limits_{i=x}^y a_i$，代价为 $(y-x+1)^2$。

输入格式

第一行，两个正整数 $n,q$，表示 DerrickLo 的属性个数与修改操作和询问的总数。

第二行，$n$ 个正整数表示序列 $a$。

接下来 $q$ 行，每行三个整数，表示一次修改操作或询问。

输出格式

设共有 $t$ 次询问，输出 $t$ 行，分别表示每次询问的答案。

3 2
1 2 3
2 1 2
2 1 1

1
0

提示

样例说明

第一次询问中，选择 $a_1$ 使其增加 $1$ 即可，代价为 $1$。

第二次询问中，由于区间大小为 $1$，所以不需要任何操作。

数据范围

对于 $100\%$ 的数据，保证输入数据全部为整数，且 $1\le n,q,a_i\le 2\times 10^5$，对于修改操作，$1\le k\le n$，$1\le x\le 2\times 10^5$；对于询问，$1\le l\le r\le n$。