Оптимальне бінарне дерево пошуку

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

Розглянемо множину $S = {e_{1}, e_{2}, ..., e_{n}}$ , яка містить $n$ різних елементів таких що $e_{1} < e_{2} < ... < e_{n}$ . Розглянемо бінарне дерево пошуку, що складається з елементів $S$ . Чим частіше відбувається запит до елементу, тим ближче він має розташовуватися до кореня.

Вартістю $cos t$ доступу до елементу $e_{i}$ з $S$ у дереві будемо називати значення $cos t (e_{i})$ , яке дорівнює кількості ребер на шляху, що сполучає корінь з вершиною, яка містить елемент. Маючи частоту запитів до елементів із $S$ , $(f (e_{1}), f (e_{2}), ..., f (e_{n}))$ , визначимо загальну вартість дерева наступним чином:

f (e_{1}) \cdot cos t (e_{1}) + f (e_{2}) \cdot cos t (e_{2}) + ... + f (e_{n}) \cdot cos t (e_{n})

Дерево, яке має найменшу вартість, вважається найкращим для пошуку елементів із $S$ . Тому воно називається Оптимальним Бінарним Деревом Пошуку.

Вхідні дані

Складається з декількох тестів, кожний з яких розташований в окремому рядку. Перше число в рядку $n (1 \leq n \leq 250)$ вказує на розмір множини $S$ . Наступні $n$ невід'ємних цілих чисел описують частоти запитів елементів з $S$ : $f (e_{1}), f (e_{2}), ..., f (e_{n}) (0 \leq f (e_{i}) \leq 100)$ .

Вихідні дані

Для кожного тесту в окремому рядку вивести вартість Оптимального Бінарного Дерева Пошуку.

Приклади

Вхідні дані #1

Відповідь #1

Відправки 1K

Коефіцієнт прийняття 44%