Balance Scale

Interview

Time limit1sMemory limit1024 MB

Summary

Stones are placed on a balance by a fixed rule, and the task asks for the fewest weights from 1g to 100g needed to level the final imbalance.

Level: Easy3 of 10
Topics: Simulation, Greedy
Solved: No attempts yet

Problem

There are $n$ stones numbered from $1$ to $n$ . Place them on a two-pan balance as follows.

Put stone $1$ on the left pan and stone $2$ on the right pan.
For each stone $i = 3, \dots, n$ $i = 3, \dots, n$ , in order, do one of the following.
1. If the balance is level, put stone $i$ on the left pan.
2. If the balance is not level, put stone $i$ on the lighter pan.

After all stones are placed by the rules above, the balance may still not be level. In that case, add weights to the lighter pan to level it. There are 7 kinds of weights: 1g, 2g, 5g, 10g, 20g, 50g, and 100g. There is no limit on the number of weights of each kind.

For the stones given in the input, find the minimum number of additional weights needed to level the balance after placing the stones by the rules above, and write a program that prints it.

Input

Standard input is used. The first line contains a positive integer $n$ ( $2 \le n \le 10\,000$ ), the number of stones. The next line contains $n$ integers, the weights of the stones in numbering order. Each stone weighs at least $1$ , and the total weight of all stones is at most $10\,000\,000$ .

Output

Standard output is used. Print the minimum number of additional weights needed to level the balance on one line.

Examples3

Example 1
Input
```
7
3 1 4 1 5 9 2
```
Expected output
```
2
```
Example 2
Input
```
4
2 4 6 4
```
Expected output
```
0
```
Example 3
Input
```
5
2 5 3 1 2
```
Expected output
```
1
```