Input
5
1 3 1 1 4
Output
5
Input
5
1 3 2 1 4
Output
4
Input
3
4 1 2
Output
0