链接: https://cses.fi/problemset/task/1191

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个由 $n$ 个数值组成的环形数组。每个元素有两个邻居；位置 $n$ 和 $1$ 上的元素也被视为邻居。

你的任务是将数组划分为若干子数组，使得每个子数组的和至多为 $k$。最少需要多少个子数组？

输入

第一行输入包含整数 $n$ 和 $k$。

下一行有 $n$ 个整数 $x_1,x_2,\ldots,x_n$：数组的内容。

总是至少存在一种划分方式（即数组中没有任何值大于 $k$）。

输出

输出一个整数：子数组的最少数量。

数据范围

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

样例输入

8 5
2 2 2 1 3 1 2 1

样例输出

3