Taulukko

• Time limit: 1.00 s
• Memory limit: 128 MB

Annettuna on syklinen taulukko, jossa on $n$ lukua. Syklisyys tarkoittaa, että kohdassa $n$ olevan luvun jälkeen tulee taas kohdassa $1$ oleva luku.

Tehtäväsi on jakaa taulukko yhtenäisiin väleihin niin, että jokaisen välin lukujen summa on enintään $k$. Mikä on pienin mahdollinen välien määrä?

Syöte

Syötteen ensimmäisellä rivillä on luvut $n$ ja $k$.

Syötteen toinen rivi sisältää $n$ lukua $x_1,x_2,\ldots,x_n$: taulukon sisältö.

Mikään taulukon luku ei ole suurempi kuin $k$.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: pienin välien määrä.

Rajat

• $1 \le n \le 10^5$
  
• $1 \le x_i \le 10^9$
  
• $1 \le k \le 10^{18}$
  

Esimerkki

Syöte:
8 5
2 2 2 1 3 1 2 1

Tuloste:
3

Selitys: Jako on seuraava: "2 | 2 2 1 | 3 1 | 2 1". Huomaa, että yksi ryhmistä jatkuu taulukon lopusta alkuun.