最高分数:1200 点
问题陈述
2212年,竞技性编程比现在更加出名,国际信息学奥林匹克(IOI)是世界上最著名的竞赛之一。
今年, N 参赛者,其ID编号为 1 to N,参加IOI。
比赛举行于 2 天数如下:
- 天 1:有纸质测试。参赛者 i 得到 A_i 点。可以保证 A_i \neq A_j (1 \leq i < j \leq N).
- 天 2:有一个实际测试。在此测试中,得分介于 将为每位参赛者授予 1 和 N 。表现最好的选手将获得 N 分,表现第二好的选手将获得 N - 1 分,...,表现最差的参赛者将获得 1 点。
目前,你知道Day-1 所有参与者的分数。但你对Day一无所知-2 结果。
在 IOI 规则中,参与者的 最终成绩 为(纸质考试成绩)+(实践考试成绩)。
的 排名 参赛者的 将确定如下:
- 基本上,最终分数越高,排名越高。 (注:最高等级为 1,最低等级是 N.)
- 若出现平局,则在得分相同的选手中随机抽签决定名次。
此外,获得排名的参赛者 1 将获得金牌,获得名次的选手 2 将获得银牌,获得名次的选手 3 将获得铜牌。
他又知道了IOI 2212最终排名的一则信息。该信息以一个整数表示 P (要么 1 or 2).
- 让 X 为获得金牌的参赛者ID。
- 让 Y 为获得银牌的参赛者ID。
- 让 Z 为获得铜牌的参赛者ID。
- If P = 1, A_X > A_Y > A_Z 满意。
- If P = 2, A_X > A_Z > A_Y 满意。
有多少种可能的组合 (X, Y, Z) 有吗?
约束
- N 是介于 5 和 1 \ 000 \ 000 (含)
- P 是 1 or 2
- A_i 是介于 1 和 1 \ 000 \ 000 \ 000 (含)
- 全部 A_i 不同。
子任务和评分
在这个问题中,有 2 子任务如下。
- (600分):P = 1
- (600分):P = 2
在每个子任务中,有 12 数据集如下。
- (50分):5 \leq N \leq 7
- (50分):5 \leq N \leq 15
- (50分):5 \leq N \leq 30
- (50分):5 \leq N \leq 70
- (50分):5 \leq N \leq 200
- (50分):5 \leq N \leq 600
- (50分):5 \leq N \leq 2 \ 000
- (50分):5 \leq N \leq 8 \ 000
- (50分):5 \leq N \leq 50 \ 000
- (50分):5 \leq N \leq 200 \ 000
- (50分):5 \leq N \leq 500 \ 000
- (50分):5 \leq N \leq 1 \ 000 \ 000
注意:在每个数据集中,可以有两个或多个测试用例。
输入
输入由标准输入按以下格式给出:
N P A_1 A_2 A_3 ... A_N
输出
打印可能的组合数 (X, Y, Z).
示例输入 1
5 1 3 1 6 4 8
示例输出 1
4
让 B_i 是这一天-2 参赛者得分 i.
有 4 方式如下。 X 是金牌得主的ID, Y ID 银牌获得者的 ID,以及 Z 是铜牌获得者的ID。
- (X, Y, Z) = (5, 3, 1)。如果 B = (3, 4, 2, 1, 5),最终得分为 6, 5, 8, 5, 13。因此,它满足条件。
- (X, Y, Z) = (5, 3, 2)。如果 B = (2, 4, 3, 1, 5),最终得分为 5, 5, 9, 5, 13。因此,根据抽签,有可能满足条件。
- (X, Y, Z) = (5, 3, 4)。如果 B = (1, 2, 3, 4, 5),最终得分为 4, 3, 9, 8, 13。因此,它满足条件。
- (X, Y, Z) = (5, 4, 1)。如果 B = (4, 2, 1, 3, 5),最终得分为 7, 3, 7, 7, 13。因此,根据抽签,有可能满足条件。
示例输入 2
5 2 6 4 1 7 2
示例输出 2
3
有 3 方式如下。
- (X, Y, Z) = (4, 2, 1)。如果 B = (1, 5, 3, 4, 2),最终得分为 7, 9, 4, 11, 4。因此,它满足条件。
- (X, Y, Z) = (4, 5, 1)。如果 B = (1, 2, 3, 4, 5),最终得分为 7, 6, 4, 11, 7。因此,根据抽签,有可能满足条件。
- (X, Y, Z) = (4, 5, 2)。如果 B = (1, 3, 2, 4, 5),最终得分为 7, 7, 3, 11, 7。因此,根据抽签,有可能满足条件。
示例输入 3
10 1 6 4 11 14 3 17 13 18 8 10
示例输出 3
26
示例输入 4
10 2 18 14 19 4 12 1 7 15 9 5
示例输出 4
14