<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

482. Impudent Thief
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



For most people Halloween evening is a time of having fun. But Mr. X chose the night after Halloween to commit a crime. He wants to get some boards to build a shed. And he decided to stole it from the fence of the neighbouring factory. But he wants to do it in such a way that nobody will notice boards loss. The fence consists of several boards with width, equal to 1, and integer heights (see picture). Mr. X is going to take some boards from the fence and then put the remaining boards together without changing their order to form a new fence. To be sure that noboby will notice the change, the perimeter of resulting fence should not be less than a half of the perimeter of initial fence. See picure description to understand the way of calculating fence's perimeter. With such constraint, Mr. X wants to maximize total height of extracted boards.



Perimeter of the fence is a perimeter of the figure, which is made by joining the rectangles corresponding to boards. For example, perimeter of the fence in the picture is marked bold and it's length is equal to 24.

Input
The first line contains integer number n (1 ≤ n ≤ 50) — number of boards in the fence. The second line contains n integer numbers hi — heights of the boards (1 ≤ hi ≤ 100). Boards are given from the leftmost one to the rightmost one.

Output
In the first line output s — maximal total height of some subset of the boards, which can be taken without violating the described rule. In the second line output k — number of boards in such subset. In the third line output k numbers of the boards which should be stolen. Boards are numbered starting from 1 as they appear in the input. Print numbers in any order. If there are multiple solutions, output any.

Example(s)
sample input
sample output
6
3 4 2 4 3 1
12
4
1 3 4 5

<|response|>
1. Abridged Problem Statement
You have n fence boards of width 1 and integer heights h₁…hₙ. The perimeter P of the assembled fence (all boards in order) is
 P = 2 + ∑_{i=1 to n−1}(2 + |hᵢ − hᵢ₊₁|) + h₁ + hₙ.
You may remove (steal) some boards and reattach the rest in the same relative order to form a new fence with perimeter P′. You must ensure P′ ≥ ⌈P/2⌉. Under that constraint, maximize the total height of boards stolen. Output that maximum sum, the count of stolen boards, and any valid set of their indices.

2. Key Observations
• Removing a board does not directly change the stolen-height sum, but it can decrease the perimeter of the remaining fence.
• The contribution to perimeter when you keep a board of height h after a previously kept board of height last is Δ = 2 + |last − h|, plus at the end you add the last board's height for the final vertical side and at the start you add h₁ for the first side.
• We want to choose which boards to keep so that the kept-fence perimeter ≥ ⌈P/2⌉, while maximizing the sum of heights of stolen boards.
• This is a classical 0/1-sequence DP: iterate boards in order, maintain (last_kept_height, current_perimeter) and track the maximum stolen-height sum.

3. Full Solution Approach
Let initP = original perimeter, target = ⌈initP/2⌉.
Define DP[pos][last][per] = maximum stolen-height sum after processing boards 1…pos, where the last kept board has height = last (0 means "none kept yet"), and the accumulated perimeter from the first kept up through pos (excluding the final right side) = per. Impossible states store −∞.
Initialization: DP[0][0][0] = 0.
Transitions for board i (height = h):
  a) Steal it:
     DP[i][last][per] → DP[i+1][last][per] with stolen_sum + h (perimeter unchanged).
  b) Keep it:
     newPer = per + 2 + |last − h|
     DP[i][last][per] → DP[i+1][h][newPer] with same stolen_sum.
After filling to pos = n, scan all states DP[n][last][per] where per + last ≥ target (add the last vertical side). Pick the state with maximum stolen_sum.
Reconstruct which boards were stolen by walking the dp table backwards (check steal vs keep transition at each step).

Time and memory: n ≤ 50, heights ≤ 100, initP ≤ ~5300 ⇒ DP size ~50×101×5300 = ~27M states, two transitions each, fits in 0.25 s in optimized C++.

4. C++ Implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int16_t MAX_HEIGHT = 101;
const int16_t MAX_PERIMETER = 5300;

int16_t n;
vector<int16_t> heights;

void read() {
    cin >> n;
    heights.resize(n);
    cin >> heights;
}

int16_t calculate_initial_perimeter(const vector<int16_t>& h) {
    int16_t perimeter = 2;
    for(int16_t i = 0; i < static_cast<int16_t>(h.size()) - 1; ++i) {
        perimeter += 2 + abs(h[i] - h[i + 1]);
    }

    perimeter += h[0] + h.back();
    return perimeter;
}

vector<int16_t> reconstruct_stolen_boards(
    const vector<vector<vector<int16_t>>>& dp, const vector<int16_t>& h,
    int16_t max_height_last_height, int16_t max_height_perimeter
) {
    vector<int16_t> stolen_boards;
    int16_t current_height = max_height_last_height;
    int16_t current_perimeter = max_height_perimeter;

    for(int16_t pos = static_cast<int16_t>(h.size()); pos > 0; --pos) {
        if(dp[pos][current_height][current_perimeter] ==
               dp[pos - 1][current_height][current_perimeter] + h[pos - 1] &&
           dp[pos - 1][current_height][current_perimeter] != -1) {
            stolen_boards.push_back(pos);
        } else {
            for(int16_t prev_height = 0; prev_height < MAX_HEIGHT;
                ++prev_height) {
                int16_t prev_perimeter =
                    current_perimeter - abs(prev_height - current_height) - 2;
                if(prev_perimeter >= 0 &&
                   dp[pos - 1][prev_height][prev_perimeter] ==
                       dp[pos][current_height][current_perimeter]) {
                    current_height = prev_height;
                    current_perimeter = prev_perimeter;
                    break;
                }
            }
        }
    }

    sort(stolen_boards.begin(), stolen_boards.end());
    return stolen_boards;
}

void solve() {
    // dp[pos][last_height][perimeter] = maximum total height of the boards
    // removed among the first pos boards, given that the rightmost kept board
    // has height last_height and the kept fence so far contributes perimeter
    // to the half-perimeter accounting (each kept board adds 2 for its top and
    // bottom plus the height difference to the previous kept board). For each
    // board we either steal it (add its height to the removed total, keeping
    // last_height and perimeter) or keep it (advance last_height and add the
    // perimeter contribution). The target is to maximise removed height while
    // the kept fence's perimeter stays at least half the original. We compute
    // the initial perimeter, set the target to ceil(initial / 2), pick the
    // best final state with perimeter + last_height >= target, then walk the
    // dp table backwards to recover which boards were stolen.

    vector<vector<vector<int16_t>>> dp(
        n + 1,
        vector<vector<int16_t>>(MAX_HEIGHT, vector<int16_t>(MAX_PERIMETER, -1))
    );
    dp[0][0][0] = 0;

    int16_t initial_perimeter = calculate_initial_perimeter(heights);
    int16_t target_perimeter = (initial_perimeter + 1) / 2;

    for(int16_t pos = 0; pos < n; ++pos) {
        for(int16_t last_height = 0; last_height < MAX_HEIGHT; ++last_height) {
            for(int16_t perimeter = 0; perimeter < MAX_PERIMETER; ++perimeter) {
                if(dp[pos][last_height][perimeter] == -1) {
                    continue;
                }

                int16_t new_height = heights[pos];
                dp[pos + 1][last_height][perimeter] = max<int16_t>(
                    dp[pos + 1][last_height][perimeter],
                    dp[pos][last_height][perimeter] + new_height
                );

                int16_t new_perimeter =
                    perimeter + abs(last_height - new_height) + 2;
                if(new_perimeter < MAX_PERIMETER) {
                    dp[pos + 1][new_height][new_perimeter] = max<int16_t>(
                        dp[pos + 1][new_height][new_perimeter],
                        dp[pos][last_height][perimeter]
                    );
                }
            }
        }
    }

    int16_t max_height = -1, max_height_perimeter = 0,
            max_height_last_height = 0;
    for(int16_t last_height = 0; last_height < MAX_HEIGHT; ++last_height) {
        for(int16_t perimeter = 0; perimeter < MAX_PERIMETER; ++perimeter) {
            if(perimeter + last_height >= target_perimeter &&
               dp[n][last_height][perimeter] > max_height) {
                max_height = dp[n][last_height][perimeter];
                max_height_perimeter = perimeter;
                max_height_last_height = last_height;
            }
        }
    }

    vector<int16_t> stolen_boards = reconstruct_stolen_boards(
        dp, heights, max_height_last_height, max_height_perimeter
    );

    cout << max_height << endl;
    cout << static_cast<int16_t>(stolen_boards.size()) << endl;
    for(int16_t index: stolen_boards) {
        cout << index << " ";
    }

    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation

```python
import sys
from math import ceil

def main():
    input_data = sys.stdin.read().split()
    n = int(input_data[0])
    heights = list(map(int, input_data[1:]))

    # Calculate initial perimeter
    P = 2
    for i in range(n-1):
        P += 2 + abs(heights[i] - heights[i+1])
    P += heights[0] + heights[-1]
    target = (P + 1) // 2

    MAX_PER = P + 1
    # dp maps (last_h, per) -> max stolen sum
    dp = {(0,0): 0}
    # back pointers: (pos, last_h, per) -> (prev_last_h, prev_per, stole?)
    back = {}

    for pos, h in enumerate(heights, start=1):
        dp_next = {}
        for (last_h, per), stolen_sum in dp.items():
            # Option 1: steal this board
            key1 = (last_h, per)
            new_sum1 = stolen_sum + h
            if dp_next.get(key1, -1) < new_sum1:
                dp_next[key1] = new_sum1
                back[(pos, key1)] = (last_h, per, True)

            # Option 2: keep this board
            new_per = per + 2 + abs(last_h - h)
            if new_per <= MAX_PER:
                key2 = (h, new_per)
                if dp_next.get(key2, -1) < stolen_sum:
                    dp_next[key2] = stolen_sum
                    back[(pos, key2)] = (last_h, per, False)

        dp = dp_next

    # Find best end state meeting the perimeter constraint
    best = (-1, None)
    for (last_h, per), stolen_sum in dp.items():
        if per + last_h >= target and stolen_sum > best[0]:
            best = (stolen_sum, (last_h, per))

    best_sum, state = best
    last_h, per = state

    # Reconstruct stolen boards
    stolen_indices = []
    pos = n
    while pos > 0:
        prev_h, prev_per, did_steal = back[(pos, (last_h, per))]
        if did_steal:
            stolen_indices.append(pos)  # 1-based
        last_h, per = prev_h, prev_per
        pos -= 1

    stolen_indices.reverse()

    print(best_sum)
    print(len(stolen_indices))
    print(*stolen_indices)

if __name__ == "__main__":
    main()
```
