题目描述

给定一个长度为 $n$ 的数列 $A$ 以及常数 $C$，你需要将其划分成若干段，然后我们依次取出每一段的段内最大值，设这样得到的序列为 $B$，你划分的段数为 $m$。

你需要最大化：

形式化的说：对于数列 $A$，你需要选择若干个下标 $1 \le p_1 < p_2 < \ldots < p_{m−1} < n$，

设 $B_1$ 为数列 $A$ 中区间 $[1, p_1]$ 的最大值，对于 $j \in [2, m − 1]$，$B_j$ 为数列 $A$ 中区间 $[p_{j−1} + 1, p_j ]$ 的最大值，$B_m$ 为数列 $A$ 中区间 $[p_{m−1} + 1, n]$ 中的最大值。

你需要最大化：

特别的，如果你划分出的段数仅有 $1$ 段，则答案为 $0$。

输入格式

从文件 array.in 中读入数据。

第一行两个整数分别表示 $n,C$。

接下来一行 $n$ 个正整数，第 $i$ 个正整数表示 $A_i$。

输出格式

输出到文件 array.out 中。

一行一个非负整数，表示答案。

样例

样例 1

5 3
10 1 2 3 5

103

样例 2

见下发文件中的 array/array2.in 与 array/array2.ans。

样例 3

见下发文件中的 array/array3.in 与 array/array3.ans。

样例 4

见下发文件中的 array/array4.in 与 array/array4.ans。

数据规模与约定

对于所有数据：$2\le n\le 10^6$，$1\le A_i\le 10^6$，$0\le C\le 10^{10}$。