---
# System prepended metadata

title: 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
```


