최적 이진 탐색 트리

검색 엔진에 사용할 서로 다른 k개의 정수 키 A1, A2, ..., Ak가 주어진다. 사용자는 1 <= s <= n인 임의의 정수 s를 검색할 수 있다.

이 키들은 이진 탐색 트리에 저장해야 한다. 각 노드는 서로 다른 키 하나를 가진다. 어떤 노드에 대해서도 왼쪽 서브트리의 모든 키는 그 노드의 키보다 작고, 오른쪽 서브트리의 모든 키는 그 노드의 키보다 크다.

검색은 루트에서 시작하며 다음 규칙을 따른다.

1. s가 현재 노드의 키와 같으면 검색에 성공하고 종료한다.
2. s가 현재 노드의 키보다 작으면 왼쪽 서브트리로 이동한다.
3. s가 현재 노드의 키보다 크면 오른쪽 서브트리로 이동한다.
4. 이동하려는 서브트리가 비어 있으면 검색에 실패하고 종료한다.

하나의 값 s를 검색할 때의 검색 횟수는 그 과정에서 방문한 트리 노드의 수이다. 트리의 효율성은 1부터 n까지의 모든 정수 s에 대한 검색 횟수의 총합으로 정의한다.

주어진 키만 포함하는 이진 탐색 트리 중 효율성이 가장 작은 경우의 총합을 구하라.

첫째 줄에 n (1 <= n <= 10,000,000)이 주어진다.

둘째 줄에 키의 개수 k (k <= 300)가 주어진다.

다음 k개의 줄에는 키 값 Ai (1 <= Ai <= 10,000,000)가 한 줄에 하나씩 주어진다. 키 값은 모두 서로 다르며, 가장 큰 키 값은 n 이하이다.

가능한 검색 횟수 총합의 최솟값을 출력한다.