양팔저울

$1$부터 $n$까지 번호가 매겨진 $n$개의 자갈이 있다. 이 자갈들을 다음 절차에 따라 양팔저울에 올려놓는다.

1. $1$번 자갈을 왼쪽, $2$번 자갈을 오른쪽에 올려놓는다.

2. $i = 3, \dots , n$번 자갈 각각에 대해서 차례로 다음 과정 중 하나를 수행한다.

   1. 만약 양팔저울이 평형을 이루는 경우, $i$번 자갈을 왼쪽에 올려 놓는다.
   2. 만약 양팔저울이 평형을 이루지 않는 경우, $i$번 자갈을 가벼운 쪽에 올려 놓는다.

모든 자갈을 위의 규칙에 따라 올려 놓은 후에도 양팔저울은 평형을 이루지 않을 수 있다. 이경우 가벼운 쪽에 무게추를 올려서 균형을 맞추려고 한다. 무게추는 1g, 2g, 5g, 10g, 20g, 50g, 100g 7종류가 있고, 무게추의 개수에는 제한이 없다.

입력 받은 자갈을 위 규칙에 따라 양팔저울에 올렸을 때, 최종적으로 평형을 맞추는데 추가적으로 필요한 무게추의 최소 개수를 구하는 프로그램을 작성하시오.

입력은 표준입력을 사용한다. 첫 번째 줄에 자갈 개수를 나타내는 양의 정수 $n$ ($2 ≤ n ≤ 10\\,000$)이 주어진다. 다음 줄에 $n$ 개의 수들이 주어지는데, 이들은 번호 순서대로 자갈의 무게이다. 자갈의 무게는 각각 $1$이상이며, 모든 자갈의 무게의 총합은 $10\\,000\\,000$이하이다.

출력은 표준출력을 사용한다. 최종적으로 평형을 맞추는데 추가적으로 필요한 무게추의 최소 개수를 한 줄에 출력한다.