该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目更新

20:14 输入格式更新

题目描述

$《祖玛》$ 是由 $Popcap Games$ 于 $2004$ 年 $1$ 月 $1$ 日开放的一款 $PC$ 端益智类系列小游戏。游戏目标是尽量消除珠子，以防止珠子滚入轨迹尽头的洞中。

鉴于机房生活过于无聊，于是 $cbh$ 在机房中玩起了祖玛。但是祖玛真太过于难了，于是 $cbh$ 决定将祖玛改造一下。

在正常的祖玛游戏中，屏幕中的石头青蛙会吐出颜色各异的珠子，与沿着一条轨迹运行的一串珠子相接，一旦三颗或以上的珠子连在一起，则这几颗珠子即可消失。这真是太麻烦了。

经过改造之后规则变为，所有球在一个 $1$ 到 $n$ 的区间中，依次赋予下标。每次青蛙会给出一个 $[l,r]$ 的区间，在这个区间中有几种颜色的球，每种颜色的球只贡献一次答案，贡献的答案为 $[l,r]$ 区间内该颜色最后一次出现位置的下标，减去第一次出现的下标。（显然的，如果只出现一次则贡献为零）。玩家要计算出正确的贡献，然后该区间的所有小球就会被打上标记，当所有小球都被打上标记后，游戏结束，玩家胜利。

但是，祖玛之神十分愤怒，他不允许有人开发出这么简单的祖玛，于是他又会在游戏中改变某些球的颜色，以此到达加大难度的目的。经过这一改变后，$cbh$ 又不会玩了。于是他决定请你帮忙写个程序进行计算，他会给出游戏中进行的所有操作，你可以帮助他吗？作为回报他会给你这场比赛的 $100$ 分作为奖励。

输入格式

第一行，两个整数 $n$ 和 $m$，分别表示有 $n$ 个小球，$m$ 次操作。

接下来一行 $n$ 个数，表示下标为 $i$ 的小球的颜色为k。

最后 $m$ 行，每行三个数 $a$ , $b$ , $c$ 。

$a$ 表示进行第几种操作。

当 $a=1$ 时，你需要输出 $[b,c]$ 区间内的贡献。

当 $a=2$ 时，表示将下标为 $b$ 的小球改为颜色 $c$。

输出格式

输出 $a=1$ 时的贡献。

样例

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

5
0
7
1

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

0
0

大样例

见附加文件的 game*.in 与 game*.out 。

下载链接：game

数据规模与约定

对于前 $20\%$ 的数据，$n$ , $m$ $\le$ $1000$ 。

对于 $100\%$ 的数据， $n$ , $m$ $\le$ $100000$ ， $k$ $\le$ $n$ ， $0$ $<$ $b$ $<$ $c$ $\le$ $n$ 。