3787. 空图

【题目描述】

给定一个序列 $a_1, a_2, \dots, a_n$ ，进行最多 $k$ 次赋值操作，然后用这个序列构造一个无向带权完全图，任意一对节点 $(l, r)$ 的边权为 $\displaystyle \min_{l \le i \le r} (a_i)$，求出最长的直径。

对于每次赋值操作：选择一个下标 $1 \le i \le n$，一个正整数 $1 \le x \le 10^9$，然后令 $a_i = x$。

图的直径：若要求得一张图的直径，首先要求得任意两点之间的最短路径，在这些所有的最短路径中，取其长度最长者，即是这张图的直径。

【输入格式】

第 $1$ 行，包括两个整数 $n, k$。 第 $2$ 行，包括 $n$ 个整数 $a_i$。

【输出格式】

输出最长直径 $ans$。

【样例输入1】

3 1
2 4 1

【样例输出1】

4

【样例输入2】

3 2
179 17 1000000000

【样例输出2】

1000000000

【样例解释】

对于样例一，一种最优序列为 $\{2, 4, 5\}$。 

$\mathrm{d}(1, 2) = \mathrm{d}(1, 3) = 2, \mathrm{d}(2, 3) = 4$，所以直径为 $\max(2, 2, 4) = 4$。

【数据规模与约定】

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^6, 1 \le k \le 1000, 1 \le a_i \le 1 \times 10^9$