Рассмотрим множество S={e1,e2,...,en}, состоящее из n различных элементов таких, что e1<e2<...<en. Рассмотрим бинарное дерево поиска, состоящее из элементов S. Чем чаще производится запрос к элементу, тем ближе он должен располагаться к корню.
Стоимостью cost доступа к элементу ei из S в дереве будем называть значение cost(ei), равное числу ребер на пути, который соединяет корень с вершиной, содержащей элемент. Имея частоту запросов к элементам из S, (f(e1),f(e2),...,f(en)), определим общую стоимость дерева следующим образом:
Дерево, имеющее наименьшую стоимость, считается наилучшим для поиска элементов из S. Именно поэтому оно называется Оптимальным Бинарным Деревом Поиска.
Состоит из нескольких тестов, каждый из которых расположен в отдельной строке. Первое число в строке n (1≤n≤250) указывает на размер множества S. Следующие n неотрицательных целых чисел описывают частоты запросов элементов из S: f(e1),f(e2),...,f(en) (0≤f(ei)≤100).
Для каждого теста в отдельной строке вывести стоимость Оптимального Бинарного Дерева Поиска.