题目内容

体育课上，老师让 $n$ 名学生按座位排成一排做分组游戏。从左到右第 $i$ 名学生手上的点数是正整数 $a_i$。一局游戏必须选一段坐在一起的学生 $[L,R]$（下标从 $1$ 开始），并且同时满足下面三条才算能开局。

• 点数之和不超过 $S$：$\sum_{i=L}^{R} a_i \le S$
• 最高点与最低点相差不能太大：$\max(a_L,\ldots,a_R)-\min(a_L,\ldots,a_R) \le D$
• 不同点数的种类数不超过 $K$：$\mathrm{distinct}(L,R) \le K$，其中 $\mathrm{distinct}(L,R)$ 表示 $[L,R]$ 里不同整数的个数

老师想知道有多少段连续座位能开局。

输入描述

第一行四个整数 $n$、$S$、$D$、$K$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

约束

$1 \le n \le 10^5$

$1 \le a_i \le 10^9$

$1 \le S \le 10^{14}$

$0 \le D \le 10^9$

$1 \le K \le n$

输出描述

输出一个整数，即能开局的连续段个数。

样例1

输入

4 4 2 2
1 2 1 3

输出

8

说明

八段能开局的座位如下。

• $[1,1]$：点数 $1$，和为 $1$，极差 $0$，一种点数
• $[1,2]$：点数 $1,2$，和为 $3$，极差 $1$，两种点数
• $[1,3]$：点数 $1,2,1$，和为 $4$，极差 $1$，两种点数
• $[2,2]$：点数 $2$，和为 $2$，极差 $0$，一种点数
• $[2,3]$：点数 $2,1$，和为 $3$，极差 $1$，两种点数
• $[3,3]$：点数 $1$，和为 $1$，极差 $0$，一种点数
• $[3,4]$：点数 $1,3$，和为 $4$，极差 $2$，两种点数
• $[4,4]$：点数 $3$，和为 $3$，极差 $0$，一种点数

$[1,4]$ 的和为 $7$，超过 $S=4$；$[2,4]$ 的和为 $6$，也超过 $S$。

样例2

输入

3 10 3 2
1 5 1

输出

3

说明

三个单人段点数分别为 $1$、$5$、$1$，都能开局。任何长度至少为 $2$ 的段都同时含有 $5$ 和 $1$，极差为 $4$，超过 $D=3$。因此答案为 $3$。