CF2053H Delicate Anti-monotonous Operations

I shall be looking for you who would be out of Existence. — HyuN, [Disorder](https://soundcloud.com/k-sounds-studio/g2r2018-hyun-disorder-feat-yuri) There are always many repetitive tasks in life. Iris always dislikes them, so she refuses to repeat them. However, time cannot be turned back; we only have to move forward. Formally, Iris has an integer sequence $ a_1, a_2, \ldots, a_n $ , where each number in the sequence is between $ 1 $ and $ w $ , inclusive. It is guaranteed that $ w \geq 2 $ . Iris defines an operation as selecting two numbers $ a_i, a_{i+1} $ satisfying $ a_i = a_{i+1} $ , and then changing them to two arbitrary integers within the range $ [1, w] $ . Iris does not like equality, so she must guarantee that $ a_i \neq a_{i+1} $ after the operation. Two identical pairs $ a_i, a_{i+1} $ can be selected multiple times. Iris wants to know the maximum possible sum of all elements of $ a $ after several (possible, zero) operations, as well as the minimum number of operations required to achieve this maximum value.

N/A

N/A

In the first test case, no operation can be performed so the answers are $ \sum a_i = 15 $ and $ 0 $ , respectively. In the second test case, the operations can be performed as follows: $ $$$[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] $ $

It can be shown this is optimal, so we should output $ \\sum a\_i = 34 $ and the number of operations, $ 6$$$, respectively.