幸福列车hard版

题目描述

注意：幸福列车(hard)和幸福列车(easy)只有数据范围不一样

‘’You're waiting for a train, a train that will take you far away. You know where you hope this train will take you, but you can't be sure. But it doesn't matter - because we'll be together.’’

--《Inception》

你在一辆通往幸福的列车上。一列开往幸福的列车需要经过$N$个站台。列车在每个站台都会发生乘客上下车，具体由序列A表示：

• 当$A_i$为正数时，表示第$i$个站台上客$A_i$人
• 当$A_i$为负数时，表示第$i$个站台下客$|A_i|$人

已知列车最大载客量为$W$，要求计算在满足以下条件时，列车在第一站出发前的初始乘客数的可能情况种数：

1. 所有时刻列车乘客数不低于$0$
2. 所有时刻列车乘客数不超过$W$

若所有初始人数都无法满足条件，输出$0$。

输入格式

• 第一行包含两个整数$N, W$ $（1\leq N \leq 10^6$) ; $1 \leq W \leq 10^5 )$
• 第二行包含$N$个整数组成的序列$A_1,A_2,...,A_N$（保证数值在int范围内）

输出格式

• 一个整数，表示可能的初始乘客数种数

示例

3 5
2 1 -3

3

2 4
-1 1

4

3 4
5 -2 -1

0

样例解释1：

初始人数为0时，列车上的人数分别为0，2，3，0，任一时刻都满足车上人数<=W以及人数>= 0

初始人数为1时，列车上的人数分别为1，3，4，1，同样满足条件

初适人数为2时，列车上的人数分别为2，4，5，2，满足条件

当初始人数大于2时，则不再满足条件

故初始人数可以为0，1，2三种情况

样例解释2：

初始人数可以为1，2，3，4四种情况

样例解释3：

因为第一站要上来5人，而最大载客量W = 4，故初始人数任何情况下都无法满足条件