An archive stores n record keys already in sorted order. Key i (1-indexed by position) is looked up f[i] times per day. You arrange the keys into a binary search tree: an in-order traversal of the tree must visit the keys in their given sorted order (so the tree's structure is a valid BST over these keys).
Looking up a key costs one comparison per node visited from the root down to it, i.e. its depth counting the root as depth 1. The daily search cost of a tree is the sum over all keys of f[i] times the depth of key i. Build the tree that minimizes this total, and report the minimum daily search cost.
Input format
Line 1: an integer n, the number of keys.
Line 2: n space-separated positive integers, the access frequencies in sorted-key order.
Output format
A single integer: the minimum total weighted search cost.
Constraints
- 1 <= n <= 200
- 1 <= each frequency <= 10000