H. Ronda com Estoque Limitado
Um veículo deve visitar exatamente uma vez os n armazéns de uma rota circular, sempre no sentido horário. Ao visitar o armazém i, seu estoque muda em ai unidades; valores positivos significam recebimento e negativos, consumo. Antes da primeira visita, o veículo tem estoque zero e não pode descartar nem comprar unidades extras.
O compartimento suporta entre 0 e C unidades, inclusive. Uma posição inicial é viável se, após cada uma das n visitas consecutivas, o estoque permanece dentro desses limites. Determine quantas posições iniciais são viáveis. A rota pode terminar com estoque diferente de zero.
Input
A primeira linha contém n C. A segunda linha contém n inteiros a1, ..., an.
Restrições:
1 ≤ n ≤ 200000; 0 ≤ C ≤ 10^15; -10^9 ≤ ai ≤ 10^9.
Output
Imprima a quantidade de posições iniciais viáveis.
Samples
Sample 1
Input
4 4 3 -2 2 -1
Output
2
Começar pelos armazéns 1 ou 3 é viável; nos demais, o estoque torna-se negativo antes do fim. Assim, existem duas posições iniciais.