题目描述

SEATST 比赛共有 $N$ 名学生参加。每名学生代表一个国家。比赛结束后，所有学生获得了互不相同的分数。

Prabowo 准备在官网上发布排行榜。对于每位学生，排行榜上列出了他们的国家、分数、总排名（global rank）和国内排名（country rank）。

• 一名学生的总排名的定义为分数高于该学生的人数。
• 一名学生的国内排名定义为与该学生同属一个国家且分数高于该学生的人数。

排行榜的示例如下：

请注意，总排名和国内排名均从 $0$ 开始，且排名不会跳号（无论是总排名还是国内排名）。

然而，当排行榜上传到网上时，Prabowo 忘记公布学生的国家和分数。对于每位学生，我们只知道他们的总排名和国内排名。

Prabowo 试图挽救这一局面，并交给你一个任务，帮助他计算以下两个数量：

• 必定属于同一个国家的学生对的数量，以及
• 必定属于不同国家的学生对的数量。

:::warning[警告]{open} 如果存在两种满足总排名和国内排名的分配方案，使得两名学生在其中一种方案中属于同一个国家，而在另一种方案中属于两个不同的国家，那么这对学生不应被计入上述任何一种计算中。 :::

请帮助 Prabowo!

实现详情

你需要实现以下两个函数。

long long count_same_country(int N, std::vector<int> country_rank)

long long count_diff_country(int N, std::vector<int> country_rank)

• $N$ ：学生人数。
• country_rank：一个长度为 $N$ 的数组，表示国内排名。对于所有 $0 \le i \le N - 1$ ， country_rank[i] 是总排名为 $i$ 的学生的国内排名。

第一个函数应返回不同学生的无序对的数量，并且每对学生都应满足在所有与排行榜相符的学生国家分配方案中均都属于同一个国家。

第二个函数应返回不同学生的无序对的数量，并且每对学生都应满足在所有与排行榜相符的学生国家分配方案中均都属于不同国家。

在每个测试数据中，这两个函数最多各被调用一次。

输入格式

输入格式：

N X
C[0] C[1] ... C[N-1]

这里的 X 可以是字符串 same（相同）或 diff（不同），从而构成 count_X_country 函数调用，且对于所有 $0 \le i \le N - 1$ ， C[i] 表示 country_rank[i]。

输出格式

一个整数表示 count_X_country 的输出结果。

提示

样例

考虑以下函数调用：

count_same_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])

假设学生 $0$、$1$ 和 $3$（为了方便起见，这里我们用学生的总排名对其进行编号）分别代表新加坡、马来西亚和印度尼西亚。

那么，下表列出了所有可能产生该排名的所有方案：

有 $4$ 对学生必定始终属于同一个国家：$(2, 4)$、$(2, 6)$、$(4, 6)$ 和 $(5, 7)$。因此，此函数应返回 $4$。

count_diff_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])

有 $17$ 对学生必定始终属于不同国家：$(0, 1)$、$(0, 3)$、$(1, 3)$、$(2, 3)$、$(2, 5)$、$(2, 7)$、$(2, 8)$、$(3, 4)$、$(3, 6)$、$(4, 5)$、$(4, 7)$、$(4, 8)$、$(5, 6)$、$(5, 8)$、$(6, 7)$、$(6, 8)$、$(7, 8)$。因此，此函数应返回 $17$。

count_same_country(5, [0, 1, 0, 1, 2])

此处有 $2$ 对学生必定始终属于同一个国家：$(0, 1)$ 和 $(2, 3)$。因此，此函数应返回 $2$。

count_diff_country(5, [0, 1, 0, 1, 2])

有 $4$ 对学生必定属于两个不同的国家：$(0, 2)$、$(0, 3)$、$(1, 2)$、$(1, 3)$。因此，此函数应返回 $4$。

约束

• $1 \le N \le 1\ 000\ 000$。
• 保证存在至少一种满足 country_rank 的学生国家分配方案。

子任务

对于前 $6$ 个子任务，只会调用 count_same_country 。

1. （$3$ 分） $N \le 8$。
2. （$6$ 分） country_rank 最多包含两个 $0$。
3. （$6$ 分） country_rank 不包含 $2$。
4. （$3$ 分） $N \le 300$。
5. （$3$ 分） $N \le 2000$。
6. （$9$ 分）没有额外的约束。

对于后 $6$ 个子任务，只会调用 count_diff_country 。

7. （$7$ 分） $N \le 8$。
8. （$14$ 分） country_rank 最多包含两个 $0$。
9. （$14$ 分） country_rank 不包含 $2$。
10. （$7$ 分） $N \le 300$。
11. （$7$ 分） $N \le 2000$。
12. （$21$ 分）没有额外的约束。