SEATST 有 $N$ 名学生。每名学生代表且仅代表一个国家。比赛结束后，所有学生的分数都各不相同。

Prabowo 即将把排行榜发布在官方网站上。对于每名学生，排行榜列出了他们的国家、分数、全球排名和国家排名。

• 学生的全球排名定义为分数高于他们的学生人数。
• 学生的国家排名定义为同一国家内分数高于他们的学生人数。

排行榜示例如下：

注意，全球排名和国家排名均从 $0$ 开始，且排名没有跳过（无论是全球还是国家内部）。

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

Prabowo 试图挽救这一局面，并委托你帮助计算两个数量：

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

警告：如果存在两种将学生分配到国家的方案，且均满足给定的全球排名和国家排名，而在其中一种方案中两名学生属于同一个国家，在另一种方案中属于不同国家，则这对学生不应计入上述任何一个数量中。

请帮助 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$ 的学生的国家排名。

第一个过程应返回满足以下条件的无序学生对数量：在所有与排行榜一致的学生国家分配方案中，这对学生始终属于同一个国家。

第二个过程应返回满足以下条件的无序学生对数量：在所有与排行榜一致的学生国家分配方案中，这对学生始终不属于同一个国家。

每个测试用例中，这两个过程最多各被调用一次。

数据范围

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

子任务

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

1. ($3$ 分) $N \leq 8$。
2. ($6$ 分) country_rank 中包含 $0$ 的次数不超过两次。
3. ($6$ 分) country_rank 不包含 $2$。
4. ($3$ 分) $N \leq 300$。
5. ($3$ 分) $N \leq 2000$。
6. ($9$ 分) 无附加限制。

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

1. ($7$ 分) $N \leq 8$。
2. ($14$ 分) country_rank 中包含 $0$ 的次数不超过两次。
3. ($14$ 分) country_rank 不包含 $2$。
4. ($7$ 分) $N \leq 300$。
5. ($7$ 分) $N \leq 2000$。
6. ($21$ 分) 无附加限制。

样例

输入格式 1

9 same
0 0 1 0 2 1 3 2 1

输出格式 1

4

说明

假设学生 $0$、$1$ 和 $3$（为方便起见，按全球排名索引学生）分别代表新加坡、马来西亚和印度尼西亚。

下表列出了产生此排名的所有可能方式：

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

输入格式 2

9 diff
0 0 1 0 2 1 3 2 1

输出格式 2

17

说明

有 $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$。

输入格式 3

5 same
0 1 0 1 2

输出格式 3

2

说明

这里有 $2$ 对学生必须始终属于同一个国家：$(0, 1)$ 和 $(2, 3)$。因此，该过程应返回 $2$。

输入格式 4

5 diff
0 1 0 1 2

输出格式 4

4

说明

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