My solution use emulation with some heuristic conditions (for avoiding deadlock). Solution is o(n).

Some test:
1
output
3
0 2 1
--------
2
output
8
1 3 4 2 0 1 3 2
--------
3
output
15
2 4 5 3 1 0 2 4 6 5 3 1 2 4 3
--------
4
output
24
3 5 6 4 2 1 3 5 7 8 6 4 2 0 1 3 5 7 6 4 2 3 5 4
--------
5
output
35
4 6 7 5 3 2 4 6 8 9 7 5 3 1 0 2 4 6 8 10 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5