I shall be looking for you who would be out of Existence.
В жизни всегда много повторяющихся задач. Ирис они всегда не нравились, поэтому она отказывается их повторять. Однако время нельзя повернуть вспять; нам нужно только двигаться вперед.
Формально, у Ирис есть целочисленная последовательность \(a_1, a_2, \ldots, a_n\), где каждое число в последовательности находится между \(1\) и \(w\) включительно. Гарантируется, что \(w \geq 2\).
Ирис определяет операцию как выбор двух чисел \(a_i, a_{i+1}\), удовлетворяющих \(a_i = a_{i+1}\), а затем изменение их на два произвольных целых числа в пределах диапазона \([1, w]\). Ирис не нравится равенство, поэтому она должна гарантировать \(a_i \neq a_{i+1}\) после операции. Каждая пара \(a_i, a_{i+1}\) может быть выбрана несколько раз.
Ирис хочет узнать максимально возможную сумму всех элементов \(a\) после нескольких (возможно, нуля) операций, а также минимальное количество операций, необходимое для достижения этого максимального значения.
Примечание
В первом наборе входных данных никаких операций не может быть выполнено, поэтому ответами являются \(\sum a_i = 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]\(\)
Можно показать, что это оптимально, поэтому мы должны вывести \(\sum a_i = 34\) и количество операций \(6\), соответственно.