Problem statement: You are given a one-dimensional array route of length n, where each cell holds a number – the cost of passing through it. The grasshopper starts immediately before the first cell and may jump one or two cells forward. Travel the whole route, arriving at the last cell, at the minimum total cost, and print the indices of the cells the grasshopper visits.

Input format: The first line contains the number n (2 ≤ n ≤ 1,000,000). The second line contains n integers, where 0 ≤ route[i] ≤ 100.

Output format: In the first line print the minimum total cost of the route. In the second line print, separated by spaces, the indices of the cells (integers from 1 to n) that the grasshopper visits on the optimal route (for example: 1 3 4 6).

Solution: The problem is solved with dynamic programming. A one-dimensional array dp is created, where dp[i] is the minimum cost of reaching cell i. Alongside it a parent array is built to reconstruct the route, where parent[i] stores the index of the previous cell on the optimal path.

Initial conditions:

dp[0] = route[0]

dp[1] = route[1]

For the remaining cells we pick the optimal move – from cell i - 1 or i - 2 – while updating the parent index:

Once the dp array is filled, the value dp[n-1] is the minimum total cost, and the parent array makes it possible to reconstruct the optimal route.

For example, given the following array:

after the computation we get:

Path reconstruction: Starting from the cell with index n - 1, follow the parent array step by step until you reach the starting position (index 0 or 1). The resulting path is then reversed to print the correct sequence of visited cells.