1. Abridged Problem Statement
Given n fence boards of width 1 and integer heights h₁…hₙ. The perimeter of the fence (joining the rectangles) is
  P = 2 + Σ_{i=1 to n–1}(2 + |hᵢ – hᵢ₊₁|) + h₁ + hₙ.
You may steal (remove) some boards and reassemble the remaining in order. Let P′ be the perimeter of the new (smaller) fence computed the same way. You must ensure P′ ≥ ⌈P/2⌉. Under this constraint, maximize the total height of stolen boards. Output that maximum sum, the count of stolen boards, and their indices (1-based).

2. Detailed Editorial

Overview
We want to choose a subset S of boards to steal so that the perimeter of the remaining boards is not less than half the original. Equivalently, we choose which boards to keep and track two quantities:
  • The sum of heights stolen (we want to maximize this).
  • The perimeter contributed by the kept boards (we want this ≥ ⌈P/2⌉).

Compute the original perimeter P in O(n). Let T = ⌈P/2⌉.

Dynamic Programming
Define DP[pos][last_h][per] = maximum total stolen height after processing the first pos boards, where:
  – last_h = height of the last kept board (or 0 if none kept yet),
  – per = perimeter accumulated so far from kept boards, *excluding* the rightmost vertical side.
Initialize DP[0][0][0] = 0, all others = –∞ (or –1 to denote impossible).

Transition for board at position pos (0-based, height = h = heights[pos]):
  1. **Steal it**:
     DP[pos+1][last_h][per] = max(DP[pos+1][last_h][per], DP[pos][last_h][per] + h)
     (stolen sum increases by h, perimeter unchanged)
  2. **Keep it**:
     new_per = per + 2 + |last_h – h|
     DP[pos+1][h][new_per] = max(DP[pos+1][h][new_per], DP[pos][last_h][per])
     (no change to stolen sum)

After filling up to pos = n, search over states DP[n][last_h][per] such that per + last_h ≥ T (we add last_h for the rightmost side). Pick the state with maximum stolen sum.

Reconstruction
Store back-pointers during the DP (or recompute by checking which transition led to the optimal). Walk backwards from pos = n, the chosen (last_h, per) to pos = 0, recording which boards were stolen.

Complexities
n ≤ 50, heights ≤ 100, original P ≤ ~5200 ⇒ DP dimension ~ 51×101×5300 ≈ 27 million states. Each has two transitions ⇒ ~54M updates. Fit into 0.25 s in optimized C++ using int16 arrays.

3. C++ Solution

```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;
}
```

4. Python Solution

```python
# Impudent Thief in Python: DP with backpointers via dictionaries.
# Note: This is a direct translation of the DP idea. For n=50 and P~5300,
# it may be slow in CPython but illustrates the approach.

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  # we'll never exceed P
    # 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)  # (stolen_sum, (last_h, per))
    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
        # move to previous
        last_h, per = prev_h, prev_per
        pos -= 1

    stolen_indices.reverse()

    # Output
    print(best_sum)
    print(len(stolen_indices))
    print(*stolen_indices)

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

5. Compressed Editorial

- Compute the original fence perimeter P.
- Let T = ceil(P/2).
- DP over positions: state (last_kept_height, current_perimeter) → max stolen-sum.
- Two transitions per board: "steal" (add height to sum, perimeter unchanged) or "keep" (increase perimeter by 2+|Δh|, sum unchanged).
- Final valid states satisfy current_perimeter + last_kept_height ≥ T.
- Pick the one with maximum stolen-sum; backtrack to find stolen indices.
