题目解析

把原序列按顺序种在一条线上。 设当前前缀和为 pre，若存在两下标 l<r 使

题目内容

新的一个季度又要到了，多多君准备在多多路上再种一些树木。

多多路上已经有了$N$棵树木(编号$1$~$N$)，对于每一棵树，多多君都给打了一个美观值评分，其中第i棵树的美观值记为$Ai$。

而对于多多路上的每个区间，其整体的美观值可以认为是该区间中每棵树的美观值之和.

多多君不太喜欢数字$M$，所以当某个区间的美观值为$M$时，就需要在该区间中再种若干树木，使得没有任何一个区间的美观值为$M$。

多多君想知道，假设新种的树木的美观值可以任意挑选的情况下，最少需要再种多少棵树，可以满足上述要求。

输入描述

共两行，第一行，两个整数N和M，分别表示当前已有树木的数量和多多君不喜欢的数字$M$。 $(1<=N<=100,000)$

$(-1,000,000<=M<=1,000,000)$

第二行，$N$个整数 $Ai$，第$i$个整数表示第$i$棵树木的美观值。

($-1,000,000 <=Ai <=1,000,000$ 且保证$Ai$不等于$M$)

输出描述

共一行，一个整数，表示最少需要再种多少树，可以满足没有任意一个区间的美观值为M的要求。

补充说明

其中$30$%的数据，有:$N<=1,000$

样例1

输入

4 -1
3 -3 2 3

输出

1

说明

只有一个区间$[2,3]$的美观值为:$-3+2=-1$不符合要求。

可以选择在$[2,3]$之间再种一颗美观值为$1$的树，使得整体为:$3\ -3\ 1\ 2\ 3$，如

此没有任何一个区间的美观值为$-1$。

样例2

输入

5 100
1 2 3 4 5

输出

0

说明

没有一个区间的和谐之和为$100$。