题目描述

小明准备帮小红大赚一笔。

小明通过未知手段，拿到了极其准确（大嘘）的接下来的 $n$ 天内某股票价格的预测变化情况。他想要劝小红在某一天购买一些股票，并在若干天后卖掉这些股票。小红是一个很胆小的人，所以小红一旦看到有一天股价低于她购入时的股价，就会立刻将手中的股票全部卖掉，立即止损。

所以小明准备依据自己的“情报”，劝小红在第 $0\sim n-1$ 天中的某一天买入一些股票，并在第 $n$ 天及以前的某一天卖掉这些股票，以此来获利。小明知道小红的性格，所以他自然不会劝小红选择会让小红进行立即止损操作的两天进行操作；并且他还知道小红不是很容易劝动，所以他定义了一个劝说难度，其等于所有可能的买入卖出的两天的组合种数，这个劝说难度数值越高，代表小明有更多的纵深可以用于劝小红。

具体地，小明需选择两天 $l,r$，满足 $0\le l<r\le n$，使得对于所有 $l<k\le r$，都有第 $k$ 天的股价不低于第 $l$ 天的股价。劝说难度就是不同的满足条件的 $(l,r)$ 对的数量。

然而，就当小明兴致勃勃地准备去找小红时，他却收到了一个新消息：有一天股价的实际变化量将比他拿到的股票变化情况大 $X$（可能为负）！小明立马又坐了下来重新分析起了这个股价的趋势。作为乐观主义者，小明想要知道，对于所有可能的差 $X$ 可能发生的日子，小明的劝说难度数值最大可能是多少。

注意，误差一定存在，最终答案可能比原始变化数据的答案小。

输入格式

第一行两个整数 $X,n$，表示那个有误差的日子的误差量，和总预测天数。

第二行 $n$ 个整数 $x_i$，表示第 $i$ 天比第 $i-1$ 天股价高了多少（可能为负）。

输出格式

一行一个整数，表示最大可能的劝说难度。

输入输出样例

样例输入1

1 6
1 1 -2 1 3 -5

样例输出1

13

样例输入2

-1 6
1 1 -2 1 3 -5

样例输出2

9

数据范围

对于 $100\%$ 的数据，$-10^9\le X,x_i\le 10^9,1\le n\le5\times10^5$。

本题采用子任务测试，且会有极大的合理子任务依赖。只有你通过了一个子任务中的所有测试点，且通过了其所有依赖子任务时，才可得到该子任务的分数。