Optimal Binary Search Tree

Time limit2sMemory limit128 MB

Summary

Given up to 300 distinct keys within range 1..n, build a binary search tree minimizing total node visits over all searches for every integer from 1 to n, using an optimal BST DP with unsuccessful search gaps.

Level: Medium6 of 10
Topics: Dynamic programming, Tree, Math
Solved: No attempts yet

Problem

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.

If s is equal to the current node's key, the search succeeds and stops.
If s is smaller than the current node's key, the search moves to the left subtree.
If s is larger than the current node's key, the search moves to the right subtree.
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.

Input

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.

Output

Print the minimum possible total search count.

Examples1

Example 1
Input
```
10
4
9
3
7
4
```
Expected output
```
22
```