You are given an array $A$ of $n$ integers. Merging 2 adjacent elements $A_i$ and $A_{i + 1}$ costs $A_i + A_{i + 1}$.
Perform the above operation until there is only $1$ element left in $A$, what is the minimum cost?
### Input
- The first line contains an integers $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Print the minimum cost.
### Constraints
- $1 \le n \le 500$.
- $1 \le A_i \le 10^9$.
### Example
Input:
```
4
10 20 30 40
```
Output:
```
190
```
The merging happens as follows (bolded elements are merged elements):
- (**10, 20**, 30, 40) → (**30**, 30, 40)
- (**30, 30**, 40) → (**60**, 40)
- (**60, 40**) → (**100**)
