Задан массив \(a\), состоящий из \(n\) целых чисел.
Скажем, что результат функции \(f(b)\) — минимальное количество операций, чтобы сделать массив \(b\) палиндромом. Операции, которые вы можете выполнять — следующие:
- выбрать два соседних элемента \(b_i\) и \(b_{i+1}\), удалить их и заменить одним элементом, равным \((b_i + b_{i + 1})\);
- или выбрать элемент \(b_i > 1\), удалить его и заменить двумя положительными целыми числами \(x\) и \(y\) (\(x > 0\) и \(y > 0\)) такими, что \(x + y = b_i\).
Например, из массива \(b=[2, 1, 3]\) за одну операцию можно получить следующие массивы: \([1, 1, 1, 3]\), \([2, 1, 1, 2]\), \([3, 3]\), \([2, 4]\) или \([2, 1, 2, 1]\).
Посчитайте \(\displaystyle \left(\sum_{1 \le l \le r \le n}{f(a[l..r])}\right)\), где \(a[l..r]\) — подотрезок массива \(a\) с \(l\)-й по \(r\)-ю позиции включительно. Другими словами — сумму значений функции \(f\) для всех подотрезков массива \(a\).