Description

汤姆想要制作一种魔力药剂，为此他购买了一批材料，每种材料包含的魔力值可能不同。汤姆将这些材料从左到右排成一排，编号分别为1、2、...、n。接下来他想要从中选出一段连续区间[L,R] （1<=L<=R<=n）,并将区间内的材料全部用于制作药剂（即编号为L、L+1、...、R的材料）。 在制作过程中，按编号次序依次加入材料，每当汤姆加入一种材料（假设该材料包含的魔力值为k），药剂的魔力值也会增加k。但是当药剂的魔力值超过最大限度M后，其魔力值就会更新为0。之后再加入新的材料，药剂的魔力值会重新从0开始累加。 请计算，有多少个区间[L,R]满足：将区间内的材料全部用于制作药剂后，药剂的魔力值不为0。

例如：n=4，这4中材料的魔力值分别为1、2、1、3；M=3，表示魔力药剂的魔力值最大限度为3。有以下区间满足要求： [1,1]、[1,2]、[1,4]、[2,2]、[2,3]、[3,3]、[4,4]，共7个。

Format

Input

第一行包含一个整数n，表示材料的数量。 第二行包含n个整数k₁,k₂,...k_n，表示每种材料包含的魔力值，整数之间以一个空格隔开。 第三行包含一个整数M，表示魔力药剂的魔力值最大限度。

Output

一个整数，表示满足题目要求的区间数量。

Samples

4
1 2 1 3
3

7

Limitation

测试点1~10：1<=n<=2*10⁵,1<=k_i<=10⁹,1<=M<=10⁹.