Optimal Binary Search Tree

You are given k distinct integer keys A1, A2, ..., Ak for a search engine. A user may search for any integer s with 1 <= s <= n.

The keys must be stored in a binary search tree. In such a tree, every node has a distinct key. For each node, every key in its left subtree is smaller than the node's key, and every key in its right subtree is larger than the node's key.

A search starts at the root.

1. If s is equal to the current node's key, the search succeeds and stops.
2. If s is smaller than the current node's key, the search moves to the left subtree.
3. If s is larger than the current node's key, the search moves to the right subtree.
4. If the subtree to move into is empty, the search fails and stops.

The search count for one value s is the number of tree nodes visited during that search. The efficiency of a tree is the sum of the search counts for every integer s from 1 to n.

Find the minimum possible efficiency among all binary search trees that contain exactly the given keys.

The first line contains n (1 <= n <= 10,000,000).

The second line contains the number of keys k (k <= 300).

Each of the next k lines contains one key value Ai (1 <= Ai <= 10,000,000). The key values are distinct, and the maximum key value is at most n.

Print the minimum possible total search count.