CF2053H Delicate Anti-monotonous Operations

生活中有许多重复的工作，Iris 不喜欢它们，然而时间不能倒流，我们只好一路向前。 说回正题，Iris 有一个数列 $a$，数列中的每个数都是 $1$ 到 $w$ 之间的正整数（保证 $w\ge 2$。）。 Iris 定义单次操作为：选择数列中相邻且相等的两个数 $a_i$ 和 $a_{i+1}$，将它们变为 $1$ 到 $w$ 之间的任意两个正整数（可以与原来相同），但是由于 Iris 不喜欢相等的数，因此修改后的 $a_i$ 和 $a_{i+1}$ 必须不等（当然，允许因为后续操作导致 $a_i$ 和 $a_{i+1}$ 与先前操作过的数相等，即操作互相独立。每对数，每个数均可操作多次）。 现在，Iris 希望知道整个数列所有数字和的最大值，以及得到这个最大值所需的最少操作次数。 保证对于每组数据所有 $a_i$ 满足 $1\le a_i\le w$， 所有数据 $n$ 的和不超过 $10^6$。

无

无

#### 样例解释 对于第一组数据，所有 $a_i$ 互不相同，无法操作，因此最大值为 $1+2+3+4+5=15$，此时操作次数为 $0$。 对于第二组数据，操作方式为： $$[3, 1, 2, 3, 4, \underline{1, 1}] \rightarrow [3, 1, 2, 3, \underline{4, 4}, 5] \rightarrow [3, 1, 2, \underline{3, 3}, 5, 5] \rightarrow [3, 1, \underline{2, 2}, 5, 5, 5] \rightarrow [3, \underline{1, 1}, 5, 5, 5, 5] \rightarrow [\underline{3, 3}, 5, 5, 5, 5, 5] \rightarrow [4, 5, 5, 5, 5, 5, 5]$$ 可以证明不存在更好的方案，此时所有数字之和为 $34$，共 $6$ 次操作。 - $1\le n\le 10^5,2\le w\le10^8$。 - 单个测试点所有数据的 $n$ 之和不超过 $10^6$。