Input
3
3 3 1
Output
12
Input
4
2 3 4 6
Output
39