## Easy splitting

For future Arena rounds we're discussing the possibility to add solutions hacking to contests : each contestant will be assigned to exactly one room where they can see solutions of every other contestant in that room, the sum of ratings of contestants in a room cannot exceed \(M\).

We want you to write the algorithm that distributes contestants to rooms : You will given a list of \(n\) positive integers \(a_1,...,a_n\) denoting the ratings of contestants, arranged in a circle (\(a_n\) is adjacent to \(a_1\)), and a positive integer \(M\).

You want to split the integers into contiguous lists such that each \(a_i\) belongs to exactly one list and the sum of elements of each list is at most \(M\). Your task is to find the minimum number of such lists in a splitting.

Note that you cannot change the order of elements \(a_i\).

#### Input Specification

The first line contains \(2\) integers \(n,M\) (\(2\leq n\leq 10^6\), \(1\leq M\leq 10^{18}\))

The next line contains \(N\) space separated integers \(a_1,...,a_n\) (\(1\leq a_i\leq M\))

#### Output Specification

Print one integer - the minimum number of lists in a valid splitting.

#### Scoring

- (3 point) \(a_i=1\).
- (6 points) \(1\leq n\leq 1000\).
- (6 points) \(M=n\) and \(a_1,...,a_n\) is a permutation of \(1,...n\).
- (8 points) \(a_{i+1}\leq a_i\) for \(1\leq i\leq n-1\).
- (7 points) No additional constraints.

#### Sample Input

```
4 10
5 3 4 5
```

#### Sample Output

`2`

## Comments

ahh I get stuck .. moncef can I get some help!

"cannot change the order of elements a" means that I cannot put the first 5 and the last 5 in the same list?

No. I think that it means you can't swap two different elements \(a_i\) and \(a_j\), in other words you can't change the ordre of the cycle \((a_1,...,a_n)\), but you can start it from any element since an \(n\)-cycle may have \(n\) representations \(((a_1,...,a_n) = (a_2,...,a_n,a_1) = (a_n,a_1,...,a_{n-1}) )\)