题目内容

农夫约翰拥有 $n$ 块连续相邻的田地，编号为 $1$ 到 $n$。每块田地有一个预期收益值 $a_i$，若为负数则表示亏损。约翰有一次技术改造的机会：他可以选择至多一块田地，将其收益值调整为 $v$（也可以不进行任何调整）。然后，他计划承包一个连续的田地区段，旨在获得最大的总收益和。所求即为：在允许至多一键调整的决策下，所有可能的连续区段的总收益和的最大值。

形式上：给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$ 和一个整数 $v$，你可以将序列中至多一个元素替换为 $v$。设最终序列为 $b_1,\dots,b_n$，求 $\max_{1 \le l \le r \le n} \sum_{i=l}^{r} b_i$ 的最大可能值。

数据范围：

• 测试用例数量 $t$ 满足 $1 \le t \le 10^5$。
• 每组数据中，$n$ 满足 $1 \le n \le 2 \times 10^5$，且所有测试用例的 $n$ 总和不超过 $2 \times 10^5$。
• $v$ 和各个 $a_i$ 均为整数，绝对值不超过 $10^9$。