清点群落

意识迷宫的群落区是一片由数据流汇聚成的湖泊。湖面上漂浮着无数光点，每个光点代表一个暗格，颜色相同的光点会自然地聚集在一起，形成一个个发光的群落。

"Zero把记忆按颜色分类。"Echo飘到湖边，投影被湖面的反光拉得很长，"每个群落是一种情绪——红色是愤怒，蓝色是悲伤，绿色是平静。我们要统计每个区间内有多少种不同的情绪。"

"咋个统计？"CC问。她的双手已经能流畅地敲击键盘了，金属手指在按键上发出清脆的声响。

"切湖。"你说，"把整片湖切成很多小段，每段的大小差不多。预先数清每小段里有多少种颜色。查询的时候，整段直接拿预存的数，零头再一只只数。"

"这像……"CC想了想，"像数模块群。先把区域分成几个大区，数清每个区里有多少种模块。问某个范围的时候，整区直接报数，零头再一只只数。"

"对。"

你开始写。先切分，然后预先数清每小段内的颜色种类。查询一个区间时，完整的段直接拿预存的值，不完整的段逐个光点数。如果某个颜色在完整的段里出现过，就不再重复统计。

屏幕上跳出了结果。第47号区间里，有47种不同的情绪。

"又是47。"CC说。

"47种情绪。"Echo说，"那是我被Zero删除之前的全部情绪。"

"全部？"你问。

"对。"Echo说，"愤怒、悲伤、平静……还有爱。"

CC没说话。但她的手指停在键盘上，像是被什么情绪击中了。

题目描述

$n$ 个数，每个数有一种颜色。$m$ 个询问，每个询问给一个区间 $[l, r]$，问区间内有多少种不同的颜色。

输入格式

$n, m$。然后 $n$ 个颜色。然后 $m$ 个询问，每行 $l, r$。

输出格式

每个询问输出不同颜色数。

输入样例

6 3
1 1 2 2 3 3
1 6 2
2 5 1
3 4 1

输出样例

1
2
1

提示

• 分块。块大小约 $\sqrt{n}$。
• 预处理每块内部的颜色种类数。
• 查询时，完整的块直接拿预处理的值，不完整的块暴力统计。

湖泊的尽头是一片矿区——不是普通的矿区，是由无数数据块堆成的矩阵。每个数据块有一个能量值，Zero会不定期给某一行或某一列的所有块同时增加或减少能量。

"要实时知道任意一个子矩阵的总能量。"Echo说，"如果每次修改都逐个块更新，太慢了。"

"分块浇水。"你说，"把整个矩阵切成很多小段，每次浇水（修改）时，如果整段都在范围内，就直接在段头上做个标记；如果只有一部分在范围内，就逐个块更新。查询的时候，把段头上的标记累加进每个块的实际值。"

"就像……"CC想了想，"给花浇水。整片花圃直接开喷头，边角的花盆单独浇。"

"对。"