Input
1 2 1 4 3 3 1 3 1 2 3 1 1 2 3 2 3 1 4 1 4 3 1 2 5 2 1 2 3 4 3 4
Output
12 24 26 24 26 13 29 29 29 31 8 19 24 19 16
Input
1 8 7 2 2 2 2 1 2 3 7 3 9 1 2 3 7 6 3 1
Output
18 27 63 51 33 9 18 27 63 33 69 9 8 12 28 18 24 4 6 9 21 12 21 3
Input
3 2 1 5 9 1 3 0 3 4 5 1 2 9 1 3 2 4 8 1
Output
50 42 25 96 28 60