e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dynamic Programming - Linear

Platforms

In older games one can run into the next situation. The hero jumps along the platforms that hang in the air. He must move himself from one side of the screen to the other. When the hero jumps from one platform to the neighboring, he spends |y2 - y1| energy, where y1 and y2 are the heights where these platforms hang. The hero can make a super jump that allows him to skip one platform, but it takes him 3 * |y3 - y1| energy.

You are given the heights of the platforms in order from the left side to the right. Find the minimum amount of energy to get from the 1-st (start) platform to the n-th (last). Print the list (sequence) of the platforms that the hero must pass.

Input

The first line contains the number of platforms n (2n100000). The second line gives n integers - the heights of the platforms, which absolute values are not grater than 400.

Output

Print in the first line the minimum amount of energy to get from the 1-st platform to the n-th. Print in the second line the number of platforms to pass. Give in the third line the list of these platforms.

Time limit 2 second
Memory limit 128 MiB
Input example #1
4
1 2 3 30
Output example #1
29
4
1 2 3 4