题目内容

在微服务网关中，为了防止某个用户短时间内发送过多请求，通常会采用最小请求间隔限流策略：即同一个用户相邻两个请求的时间戳之差必须大于等于 $minInterval$ 秒。例如，若 $minInterval = 2$，则请求时间戳为 $1$ 和 $3$ 可以同时通过（差为 $2$），但 $1$ 和 $2$ 不能同时通过（差为 $1$）。

现有一批属于同一用户的请求，每个请求带有一个时间戳（单位：秒，整数）。网关需要从这批请求中挑选一部分放行，使得任意两个被放行的请求时间差都 $≥ minInterval$。请你计算一共有多少种合法的放行方案（包括空集）。

例如，请求时间戳为 $[1, 3, 4]$，$minInterval = 2$，则合法的放行方案有：$[]$、$[1]$、$[3]$、$[4]$、$[1,3]$、$[1,4]$，共 6 种（注意 $[3,4]$ 非法，因为差为 $1 < 2$）。

输入描述

输入格式

• $int[]$ $timestamps$：整数数组，表示每个请求的时间戳（可能乱序，无重复）。
• $int$ $minInterval$：最小允许的请求间隔（秒），$minInterval ≥ 1$。

输出描述

• 输出格式
  • $int$：合法放行方案的总数。

数据规模

• $1 ≤ timestamps.length ≤ 15$
• 时间戳取值范围：$0 ≤ timestamp ≤ 10^9$
• $minInterval$ 为正整数

样例1

输入

[1,2,4],2

输出

6

说明

合法方案：$[]$、$[1]$、$[2]$、$[4]$、$[1,4]$、$[2,4]$，共 $6$ 种

样例2

输入

[10],5

输出

2

说明

合法方案：$[]$、$[10]$，共 $2$ 种