비용이 큰 이진 탐색

여러분은 모든 알고리즘 중에서도 가장 중요하다고 할 만한 알고리즘인 이진 탐색을 구현하라는 요청을 받았다. 더 정확히 말하면, 정렬된 객체 배열과 그 배열에 삽입하려는 새 객체가 있다. 삽입 위치를 찾기 위해 자신의 객체를 배열의 객체들과 비교할 수 있다. 각 비교는 자신의 객체가 비교 대상 객체의 오른쪽에 삽입되어야 한다는 뜻인 "큼"이나, 자신의 객체가 비교 대상 객체의 왼쪽에 삽입되어야 한다는 뜻인 "작음" 중 하나를 반환할 수 있다. 단순화를 위해 이 문제에서 비교는 절대로 "같음"을 반환하지 않는다. 자신의 객체가 배열의 어떤 객체보다 크다면 그 객체의 왼쪽에 있는 모든 객체보다도 크며, 마찬가지로 자신의 객체가 배열의 어떤 객체보다 작다면 그 객체의 오른쪽에 있는 모든 객체보다도 작다는 것이 보장된다. 배열에 n개의 원소가 있다면 알고리즘에는 n+1개의 가능한 결과가 있다.

이 문제에서는 모든 비교의 비용이 같지는 않다. 더 정확히 말하면, 자신의 객체를 배열의 i번째 객체와 비교하는 비용은 $a_{i}$이며, 이는 1 이상 9 이하의 정수이다.

이진 탐색의 최악의 경우 총비용은 얼마인가? 최적의 전략을 따르며 최악의 경우의 총비용을 최소화하려 한다고 가정한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 50. 모든 자릿값은 1 이상 9 이하이다. 한 줄의 숫자들 사이에는 공백이 없다.

작은 데이터 세트

시간 제한: 240초. 1 ≤ n ≤ $10^{4}$.

큰 데이터 세트

시간 제한: 480초. 1 ≤ n ≤ $10^{6}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 하나의 테스트 케이스에 대한 비교 비용 $a_{i}$을 나타내는 하나의 숫자열이 들어 있다. 배열의 크기 n은 이 숫자열의 길이로 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 최악의 경우의 이진 탐색 총비용이다.