题目描述

有 $n$ 件物品按顺序排成一行，每件物品的重量都是 $0$ 到 $H$ 之间的整数。

现有 $n-1$ 条称重记录，第 $i$ 条记录记载：第 $i$ 件和第 $i+1$ 件物品的重量之和为 $b_i$。这些记录可能自相矛盾。你可以删除其中的一些记录，使剩下的记录都能成立。

具体地，删除后必须存在一组整数重量 $w_1,\ldots,w_n$，满足 $0\le w_i\le H$，且每条保留的记录 $i$ 都满足 $w_i+w_{i+1}=b_i$。

求最少需要删除多少条记录。

输入格式

第一行包含两个整数 $n,H$。

若 $n>1$，第二行包含 $n-1$ 个整数 $b_1,b_2,\ldots,b_{n-1}$。

输出格式

输出一个整数，表示最少需要删除的记录数。

样例

输入

5 1
0 2 0 2

输出

2

样例解释

删除第二、第四条记录，并令所有物品的重量均为 $0$，剩下的记录就能成立。最少需要删除两条记录。

数据范围

对于所有测试点，$1\le n\le2\times10^5$，$1\le H\le10^9$，$0\le b_i\le2H$，所有输入数值均为整数。