题目描述

最近有人送给文景一条狗，这条狗的名字叫酷漫。现在文景有很多烦恼，例如酷漫喜欢散步。

根据经验文景了解到，为了一切良好，酷漫需要连续两天至少散步K次。

例如 \(K=5\)，如果文景和酷漫今天一起散步了两次，那么明天他至少要带着酷漫散步 \(3\) 次。

文景分析了他接下来的 \(N（1≤N≤2×10^5）\) 天里所有要完成的事情，并制作了一个由 \(N\) 个整数 \(（a_1,a_2,…,a_i,…,a_N）\) 组成的序列，\(a_i\) 表示第 \(i\) 天处理所有事情时与酷漫同行的次数。（例如，他必须去商店、扔掉垃圾等）

请你帮助文景确定接下来的N天里，他需要额外散步的最少次数。使得酷漫在所有 \(N\) 天里都会感觉良好。你可以假设在第 \(1\) 天的前一天和第 \(2\) 天的后一天，文景将于酷漫一起散步整整 \(K\) 次。

格式

输入格式

第一行包含两个正整数N和K，以空格隔开。

第 \(2\) 行包含 \(a_1,a_2,…,a_i,…,a_N\) 序列，以空格隔开。

输出格式

一行一个正整数，表示文景需要额外散步的最少次数。

样例1

样例输入1

3 5
2 0 1

样例输出1

4

限制

时间：\(1s\) 空间：\(256M\)

对于 \(20\%\) 的数据：\(1≤N≤12；1≤K≤4\)；

对于 \(50\%\) 的数据：\(1≤N≤10^4；1≤K≤10^4\)；

对于 \(100\%\) 的数据：\(1≤N≤2×10^5；1≤K≤10^4；0≤a_i≤K\)；

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)