---

题目回顾

给定数组 $a_1, a_2, \dots, a_n$，元素均为正整数。
可以选一些位置染红，要求不能有相邻红位置。
得分定义为：

$$\text{score} = \max(\text{红色元素}) + \min(\text{红色元素}) + \text{红色元素个数} $$

求最大可能得分。

---

第一步：最优解必然包含全局最大值

设全局最大值为 $M = \max(a)$。
假设某个最优解中，红色元素的最大值 $m < M$。
那么我们可以加入任意一个值为 $M$ 的位置（如果相邻位置有红，则删掉那个红，最多删 $2$ 个）。
这样变化后：

• 最大值从 $m$ 变成 $M$，增加了 $M - m \ge 1$。
• 元素个数最多减少 $2$。
• 最小值不变或可能变大（如果删掉的是最小值，最小值可能变大，但不会让分数变小）。

所以新分数 $\ge$ 旧分数 $+ (M - m) - 2$。
当 $M - m \ge 2$ 时，新分数严格更大；当 $M - m = 1$ 时，新分数至少不变。
因此最优解中一定存在某个红色元素等于 $M$。

---

第二步：枚举最小值 $l$，维护可选区间

设 $r = M$ 固定。
我们考虑所有 $a_i \in [l, r]$ 的位置。
这些位置被允许选，并且它们必须包含至少一个 $a_i = r$。

问题转化为：

在数组的某些位置（$a_i \in [l, r]$）中选一个子集，不能相邻，必须包含至少一个 $r$，最大化：

$$r + l + \text{所选个数}$$

因为 $r$ 固定，我们要最大化 $l + \text{所选个数}$。

---

第三步：对每个 $l$，如何计算最大可选个数？

允许的位置把数组分成若干连续段（connected components）。
在一个长度为 $s$ 的连续段中，不能相邻选，最多选 $\lceil s/2 \rceil$ 个。

那么如果不考虑必须选 $r$，总个数为：

$$\text{total}(l) = \sum_{\text{每个段}} \lceil \text{段长} / 2 \rceil $$

---

第四步：保证至少选一个 $r$

如果某个段里包含 $r$，那么选 $\lceil s/2 \rceil$ 个时，可能包含 $r$，也可能不包含。
能不能保证包含 $r$？

关键观察：

• 在一个段里，如果固定选 $\lceil s/2 \rceil$ 个，有两种“极值”选法：
  从第一个位置开始选（奇偶性 1），或者从第二个位置开始选（奇偶性 2）。
• 一个段里的某个具体位置 $p$（从段头数第 $k$ 个）能被包含在“最多选”方案中，当且仅当：
  要么选奇数位置，要么选偶数位置，并且 $p$ 属于被选的那一组。

因此：

• 如果 $r$ 在某个段里，并且它可以在奇数位置被选到（即段头到它的距离是偶数，从 $0$ 开始计），则这个段可以通过选择奇数位置来包含 $r$。
• 同样，如果 $r$ 在偶数位置被选到（距离是奇数），则选偶数位置即可包含 $r$。

所以对于包含 $r$ 的段，有两种选法（奇/偶）。
我们要看：是否存在一个段，使得它的两种选法之一同时满足：

1. 该段选了 $\lceil s/2 \rceil$ 个元素（最大个数）。
2. 包含 $r$。

---

第五步：维护两个布尔值

对每个段，维护：

• can_odd：是否可以通过选奇数位置（从段头 1 开始）包含 $r$。
• can_even：是否可以通过选偶数位置包含 $r$。

如果某个段里，$r$ 出现在奇数位置（段内索引从 1 开始），那么 can_odd = true；
如果出现在偶数位置，那么 can_even = true。
（注意：如果段里 $r$ 出现多次，可能两个都 true。）

---

第六步：全局判断能否包含 $r$

若所有段中，奇数选法都不包含 $r$，且偶数选法也都不包含 $r$，则必须放弃一个段的一个元素来换 $r$，总个数减 1。

否则，我们可以选择一种选法（奇或偶），使得每个段都取 $\lceil s/2 \rceil$，且至少一个段包含了 $r$。

---

第七步：枚举 $l$ 的过程

我们从大到小枚举 $l$（从 $r$ 往下到最小值），同时维护 DSU（并查集）来合并相邻的“可选”段。

当 $l$ 减小时，新加入一些位置 $a_i = l$，这些位置可能：

• 单独成一个段，
• 或连接左右两个段（如果它们已经是可选状态）。

每次合并时更新：

• 段长
• can_odd 和 can_even（根据 $r$ 在当前段内的位置合并）

然后计算：

$$\text{score}(l) = r + l + \text{total}(l) - \delta $$

其中 $\delta = 1$ 如果“无法在保持最大个数下包含 $r$”，否则 $\delta = 0$。

---

第八步：复杂度

每个位置被加入一次，合并用 DSU 并查集，总复杂度 $O(n \alpha(n))$。

---

最终算法步骤

1. 找到全局最大值 $r = \max(a)$。
2. 按值从大到小枚举 $l$（去重）。
3. 维护一个布尔数组 active，标记 $a_i \ge l$。
4. 当 $l$ 减小，新激活的位置尝试与左右合并（DSU）。
5. 每个 DSU 节点维护：
   • 段长
   • has_r_odd：段内是否存在 $r$ 在奇数位置（从段头 1 开始数）
   • has_r_even：段内是否存在 $r$ 在偶数位置
6. 全局维护：
   • total_odd：所有段的奇数选法的总数（即 $\sum \lceil s/2 \rceil$）
   • total_even：所有段的偶数选法的总数（其实等于 total_odd，因为 $\lceil s/2 \rceil$ 与奇偶无关，但区别在于包含 $r$ 的可能性）
7. 全局检查：是否存在一个段，其 has_r_odd = true，或者 has_r_even = true？
   若没有，则答案 $= r + l + \text{total} - 1$；
   否则 $= r + l + \text{total}$。
8. 取所有 $l$ 的最大值。

---

示例验证（第三组数据）

数组：$[3,3,3,3,4,1,2,3,5,4]$，$r=5$。

• 当 $l=5$：只有 $5$ 一个元素，段长 1，可选 1 个，包含 $r$，得分 $=5+5+1=11$。
• 当 $l=4$：可选 $4,5,4$，位置 5 的 4 和位置 10 的 4 与位置 9 的 5 形成两个段？ 不对，检查：
  激活位置：5(4), 9(5), 10(4) → 实际上位置 5 与位置 9 不相邻，所以段是 [5] 和 [9,10]。
  段1: [5] 长1 → 可选1，$r$ 不在。
  段2: [9,10] 长2 → 可选1（奇数选法取9，偶数取10），$r$ 在 9（奇数位），所以 has_r_odd=true。
  总数=1+1=2，可以包含 $r$，得分=5+4+2=11。
• 当 $l=3$：激活很多，计算得最大 12。

最终答案 12，匹配样例。

---

总结

本题核心：

1. 固定最大值 $r$ 必选。
2. 枚举最小值 $l$，用 DSU 维护可选段。
3. 每个段最多选 $\lceil s/2 \rceil$ 个，奇偶两种选法。
4. 检查是否能包含 $r$，不能则总个数减 1。
5. 取 $\max(r + l + \text{count})$。

复杂度 $O(n \log n)$ 或 $O(n \alpha(n))$，可以过 $2\times 10^5$。