[R74C]中继站迁移方案 - 代码源竞赛平台

时空限制

2S/256M

题目描述

一条直线通信线路上设置了 $n$ 座位于整数坐标的中继站。为了满足相邻中继站的通信距离上限，维护人员必须恰好迁移一座非端点中继站，两端枢纽保持不动。需要统计所有合法的“所选中继站与新坐标”方案。

形式化地，数轴上有 $n$ 个点，整数坐标满足 $a_1<a_2<\cdots<a_n$。另给定一个正整数 $k$。

必须恰好进行一次移动：选择下标 $i$，其中 $2\le i\le n-1$，把坐标为 $a_i$ 的点移动到整数坐标 $x$。要求 $a_1<x<a_n$，且 $x$ 不等于移动前任意一个点的坐标，包括被移动点原来的坐标 $a_i$。两个端点不能移动。

移动后重新按坐标从小到大排列所有点。如果任意两个相邻点的距离都不超过 $k$，则此次移动合法。

求合法移动的数量。两次移动当且仅当所选下标 $i$ 或目标坐标 $x$ 不同时视为不同。

格式

输入格式

第一行包含两个整数 $n,k$，表示中继站的个数和限制的距离。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个中继点的坐标。

输出格式

输出一个整数，表示合法移动的数量。

样例

样例输入 #1

4 4
0 2 5 9

样例输出 #1

4

样例解释 #1

合法移动为 $(i,x)=(2,1),(2,3),(2,4),(3,6)$。

样例输入 #2

3 2
0 1 5

样例输出 #2

0

样例解释 #2

移动后仍只有一个内部点，无法使两个相邻间距都不超过 $2$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	依赖	特殊性质
$1$	$20$		$n=3$
$2$	$80$	$1$	无特殊限制

对于 $100\%$ 的数据，满足 $3 \le n \le 60$，$1 \le k \le 1000$，$0 \le a_1<a_2<\cdots<a_n \le 1000$。