题目描述

东科迪勒拉山脉是安第斯山脉的一部分，横跨玻利维亚。它由一系列的 $N$ 个山峰组成，编号从 $0$ 到 $N-1$。山峰 $i$（$0 \leq i < N$）的高度为 $H[i]$，是一个介于 $1$ 到 $N-1$（包含两端）之间的整数。

对于任意两个山峰 $i$ 和 $j$（其中 $0 \leq i < j < N$），它们之间的距离定义为 $d(i, j) = j - i$。

根据古代印加传说，一组山峰的三元组是神秘的，如果它具有以下特殊性质：三个山峰的高度忽略顺序后与它们两两之间的距离匹配。

形式上，一组索引 $(i, j, k)$ 是神秘的，如果：

• $0 \leq i < j < k < N$，并且
• 高度 $(H[i], H[j], H[k])$ 忽略顺序后与两两之间的距离 $(d(i, j), d(i, k), d(j, k))$ 匹配。例如，对于索引 $0, 1, 2$，两两之间的距离为 $(1, 2, 1)$，所以高度 $(H[0], H[1], H[2]) = (1, 1, 2)$、$(H[0], H[1], H[2]) = (1, 2, 1)$ 和 $(H[0], H[1], H[2]) = (2, 1, 1)$ 都与它们匹配，但高度 $(H[0], H[1], H[2]) = (1, 2, 2)$ 则不匹配。

本题由两部分组成，每个子任务分别与第一部分或第二部分相关。你可以按任意顺序解决这些子任务。特别地，你不需要完成第一部分的所有内容后再尝试第二部分。

第一部分

给定山脉的描述，你的任务是统计神秘三元组的数量。

实现细节

你需要实现以下函数：

long long count_triples(std::vector<int> H)

• $H$：长度为 $N$ 的数组，表示山峰的高度。
• 对于每个测试用例，该函数会被恰好调用一次。

该函数应返回一个整数 $T$，即山脉中神秘三元组的数量。

第二部分

你的任务是构造具有许多神秘三元组的山脉。这部分包含 6 个仅输出的子任务，采用部分计分方式。

在每个子任务中，会给你两个正整数 $M$ 和 $K$，你需要构造一个山峰数量不超过 $M$ 的山脉。如果你的解决方案包含至少 $K$ 个神秘三元组，你将获得该子任务的满分。否则，你的得分将与你的解决方案中包含的神秘三元组数量成比例。

注意，你的解决方案必须是一个有效的山脉。具体来说，假设你的解决方案有 $N$ 个山峰（$N$ 必须满足 $3 \leq N \leq M$）。那么，山峰 $i$（$0 \leq i < N$）的高度 $H[i]$ 必须是一个介于 $1$ 到 $N-1$（包含两端）之间的整数。

实现细节

有两种提交解决方案的方式，对于每个子任务，你可以选择其中任意一种：

• 输出文件
• 函数调用

要通过输出文件提交解决方案，请创建并提交一个如下格式的文本文件：

N
H[0] H[1] ... H[N-1]

要通过函数调用提交解决方案，你需要实现以下函数：

std::vector<int> construct_range(int M, int K)

• $M$：最大山峰数量。
• $K$：期望的神秘三元组数量。
• 对于每个子任务，该函数会被恰好调用一次。

该函数应返回一个长度为 $N$ 的数组 $H$，表示山峰的高度。

输入格式

第一部分和第二部分使用相同的样例评测程序，两部分的区别由输入的第一行决定。

第一部分的输入格式：

1
N
H[0] H[1] ... H[N-1]

第二部分的输入格式：

2
M K

输出格式

第一部分的输出格式：

T

第二部分的输出格式：

N
H[0] H[1] ... H[N-1]

注意，样例评测程序的输出与第二部分的输出文件格式一致。

输入输出样例 #1

输入 #1

1
7
4 1 4 3 2 6 1

输出 #1

3

说明/提示

第一部分示例

考虑以下调用：

count_triples([4, 1, 4, 3, 2, 6, 1])

该山脉中有 3 个神秘三元组：

• 对于 $(i, j, k) = (1, 3, 4)$，高度 $(1, 3, 2)$ 与两两之间的距离 $(2, 3, 1)$ 匹配。
• 对于 $(i, j, k) = (2, 3, 6)$，高度 $(4, 3, 1)$ 与两两之间的距离 $(1, 4, 3)$ 匹配。
• 对于 $(i, j, k) = (3, 4, 6)$，高度 $(3, 2, 1)$ 与两两之间的距离 $(1, 3, 2)$ 匹配。

因此，该函数应返回 $3$。

注意，索引 $(0, 2, 4)$ 不构成神秘三元组，因为高度 $(4, 4, 2)$ 与两两之间的距离 $(2, 4, 2)$ 不匹配。

第一部分约束

• $3 \leq N \leq 200000$
• 对于每个 $i$（$0 \leq i < N$），$1 \leq H[i] \leq N - 1$。

子任务与计分

第一部分共 70 分。

子任务	分值	附加约束
1	8	$N \leq 100$
2	6	对于每个 $i$（$0 \leq i < N$），$H[i] \leq 10$。
3	10	$N \leq 2000$
4	11	高度是非递减的。即对于每个 $i$（$1 \leq i < N$），$H[i - 1] \leq H[i]$。
5	16	$N \leq 50000$
6	19	无附加约束。

第二部分共 30 分。对于每个子任务，$M$ 和 $K$ 的值是固定的，如下表所示：

子任务	分值	$M$	$K$
$7$	$5$	$20$	$30$
$8$		$500$	$2000$
$9$		$5000$	$50000$
$10$		$30000$	$700000$
$11$		$100000$	$2000000$
$12$		$200000$	$12000000$

对于每个子任务，如果你的解决方案不是一个有效的山脉，你的得分将为 $0$。

否则，设 $T$ 为你的解决方案中神秘三元组的数量。那么，你在该子任务的得分是：

$$\begin{aligned} 5 \cdot \min \left(1, \frac{T}{K}\right) \end{aligned} $$