清查暗格

意识迷宫的入口隧道两侧，嵌满了发光的储物格——不是物质的，是数据凝结成的暗格。每个暗格里存着一段记忆碎片，颜色各异。有些是Zero的，有些是Echo的，还有些是三年前那些被清洗的人的。

"我们要找到重复的记忆。"Echo飘到一面墙前，投影被暗格的彩光染成了彩虹色，"Zero把重要的记忆复制了很多份，藏在不同的暗格里。只有找到颜色相同的暗格，才能拼出完整的画面。"

"咋个找？"CC问。她的双手在键盘上悬停——左手还不太灵活，但已经能敲击了。

"不能直接暴力搜。"你说，"暗格太多了。要回答很多个询问——每个询问给你一个区间，问这个区间里随机抽两个暗格，颜色相同的概率是多少。"

"概率？"CC皱眉。

"对。如果区间里有 $cnt_c$ 个颜色为 $c$ 的暗格，那么抽到同色的概率就是所有颜色的 $cnt_c \times (cnt_c-1)$ 之和，除以总的抽取方式。"

"那一个个数？"

"不。把暗格切成很多小段，每段大小差不多。先把所有询问按左端点所在的段归类，同一段内按右端点排好。然后用两个指针在序列上滑动，每次只移动一个位置，维护当前区间内每种颜色的数量。"

CC看着你画的切分示意图，忽然说："这像翻书。先翻到某一章，然后在章内一行行读。"

"对。"

你开始写。先切分，再归类询问，然后双指针滑动。每次指针移动时，只需要更新一个暗格的颜色计数——移出去就减一，移进来就加一。

屏幕上跳出了结果。第47号区间里，颜色相同的概率是100%。

"100%？"CC瞪眼。

"说明这个区间里的暗格全是同一种颜色。"Echo说，"全是我。"

题目描述

$n$ 个暗格，每个有一种颜色。$m$ 个询问，每个询问给一个区间 $[l, r]$，问区间内随机抽两个暗格颜色相同的概率。

输入格式

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

输出格式

每个询问输出概率（最简分数或小数）。

输入样例

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

输出样例

1/5
1/6
0/1
1/6

提示

• 分块（莫队算法）。块大小约 $\sqrt{n}$。
• 询问按左端点所在块排序，同一块内按右端点排序。
• 双指针滑动，维护当前区间内每种颜色的数量。

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

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

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

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

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

"对。"