Hopper 135 With Answer

# Hopper 135 With Answer We are given an array $a$ of size $n$. At the beginning of the array, just before the ﬁrst cell, a hopper is seated. He is able to jump on the next cell and also jump over 2 cells and over 4 cells, i.e. from cell $i$ he can jump to cells $i+1$, $i+3$ and $i+5$. When the hopper occurs on a cell, he gets the number of candies that is written in the cell of the array $a$. The hopper wants to get as many candies as possible and ﬁnish its jumps on the last cell. It is to ﬁnd such a maximal number of candies and a way of the hopper to achieve the maximum. Note that there may be a negative number of candies written in some cell. ## Input format The ﬁrst line contains one integer $n$ ($1 \le n \le 10^5$) — the length of the array. The second line contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$) — the number of candies in each cell. ## Output format In the ﬁrst line print two integers — the maximum sum and number $q$ of cells visited by the hopper to achieve this maximum. In the second line print $q$ integers. The $i$-th integer is the cell visited by the hopper after $i$-th jump. Consecutive cells should be reachable by the hopper’s jump, the ﬁrst cell should be reachable from cell $0$, the last cell should be the rightmost cell. If there is more than one optimal way, print any of them. ## Sample ### Input ``` 5 4 7 6 6 6 ``` ### Output ``` 29 5 1 2 3 4 5 ```