题目背景

本题目前可以评测子问题 1。可在 P13553 评测子问题 2。

题目描述

东科迪勒拉山脉是安第斯山脉跨越玻利维亚的部分。它由连续的 $N$ 座山峰组成，从 $0$ 到 $N - 1$编号。山峰 $i$（$0 \leq i < N$）的高度 $H[i]$ 是 $1$ 到 $N - 1$ 之间的整数。

对任意两座山峰 $i$ 和 $j$（其中 $0 \le 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)$ 都匹配，但山峰高度 $(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$ 的高度 $H[i]$（$0 \leq i < N$）必须是一个 $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
7
4 1 4 3 2 6 1

3

提示

子问题 1 例子

考虑以下调用。

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)$ 并不匹配。

子问题 1 数据范围

• $3 \leq N \leq 200\,000$。
• 对每个满足 $0 \le i < N$ 的 $i$，都有 $1 \leq H[i] \leq N-1$。

子任务与得分规则

子问题一总共 $70$ 分。

子任务	分数	额外的约束条件
1	$8$	$N \leq 100$
2	$6$	对每个满足 $0 \leq i < N$ 的 $i$，都有 $H[i] \leq 10$。
3	$10$	$N \leq 2000$
4	$11$	山峰的高度是单调不下降的。 也就是说，对每个满足 $1 \leq i < N$ 的 $i$ 都有 $H[i - 1] \leq H[i]$。
5	$16$	$N \leq 50\,000$
6	$19$	没有额外的约束条件。

子问题二总共 $30$ 分。 每个子任务的 $M$ 和 $K$ 值是固定的，如下表所示：

子任务	分数	$M$	$K$
7	$5$	$20$	$30$
8		$500$	$2000$
9		$5000$	$50\,000$
10		$30\,000$	$700\,000$
11		$100\,000$	$2\,000\,000$
12		$200\,000$	$12\,000\,000$

对每个子任务，如果你的答案不构成有效的山脉，你的得分将为 $0$（在 CMS 中被报告为 Output isn't correct）。否则，设 $T$ 表示答案中的神话三峰数量。 则你在该子任务中的得分为：

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