题目描述

在无尽的时空裂隙中，漂浮着一串由 $n$ 个能量节点组成的序列，从左到右编号为 $1$ 到 $n$。每个节点拥有一个能量值，范围为 $1$ 到 $n$ 的整数，不同节点可以有相同的能量值。对于序列中的某个连续子段，定义能量值 $x$ 的跨度为该能量值在该子段中最后一次出现的位置与第一次出现的位置之差。整个子段的总跨度等于该子段中所有出现过能量值的跨度之和。能量节点的能量值会随着时间波动，总跨度也随之变化。有时需要回溯特定子段的历史轨迹，请你计算每个查询子段的总跨度。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示节点数量和操作总次数。
第二行包含 $n$ 个整数 $a_i$，表示初始时第 $i$ 个节点的能量值。
接下来 $m$ 行，每行是以下两种操作之一：
$1$ $p$ $x$ ：将第 $p$ 个节点的能量值改为 $x$。
$2$ $l$ $r$：查询子段 $[l,r]$的总跨度。

输出格式

对于每个查询操作，输出一行一个整数，表示该子段的总跨度。

样例

7 6
1 2 3 1 3 2 1
2 3 7
2 1 3
1 7 2
1 3 2
2 1 6
2 5 7

5
0
7
1

7 5
1 3 2 1 4 2 3
1 1 4
2 2 3
1 1 7
2 4 5
1 1 7

0
0

数据范围

对于$30$%的数据

• $1<=n,m<=1000$

对于$100$%的数据

• $1<=n,m<=10^5$
• $1<=p,x,a_i<=n$
• $1<=l<=r<=n$
  保证其中 $20$%的数据没有修改操作