impl Solution {
    pub fn construct_distanced_sequence(n: i32) -> Vec<i32> {
        let size = (2 * n - 1) as usize;
        let mut seq = vec![0; size]; // Sequence of length 2n - 1
        let mut used = vec![false; (n + 1) as usize]; // Tracks used numbers

        // Start backtracking
        if !Self::backtrack(0, &mut used[..], &mut seq[..]) {
            panic!("No valid sequence exists"); // Should never occur per problem constraints
        }
        seq
    }

    fn backtrack(pos: usize, used: &mut [bool], seq: &mut [i32]) -> bool {
        // If we've filled the sequence, return success
        if pos >= seq.len() {
            return true;
        }

        // Skip already placed numbers and move forward
        if seq[pos] != 0 {
            return Self::backtrack(pos + 1, used, seq);
        }

        let n = used.len() - 1; // Infer `n` from `used` length

        // Try placing numbers from largest to smallest (ensuring lexicographical order)
        for num in (1..=n).rev() {
            if used[num] {
                continue; // Skip numbers already in use
            }

            // Place the number if valid
            if Self::place_value(seq, pos, num as i32) {
                used[num] = true;
                if Self::backtrack(pos + 1, used, seq) {
                    return true; // If successful, return immediately
                }
                Self::remove_value(seq, pos); // Undo placement if it leads to a dead-end
                used[num] = false;
            }
        }
        false // No valid placement found at this position
    }

    fn place_value(seq: &mut [i32], pos: usize, num: i32) -> bool {
        if seq[pos] != 0 {
            return false; // Position already occupied
        }
        if num == 1 {
            seq[pos] = num; // 1 appears only once
            return true;
        }
        let second_pos = pos + num as usize;
        if second_pos < seq.len() && seq[second_pos] == 0 {
            seq[pos] = num;
            seq[second_pos] = num; // Place number at correct distance
            return true;
        }
        false // Placement not possible
    }

    fn remove_value(seq: &mut [i32], pos: usize) {
        let num = seq[pos];

        // Ensure we are removing a valid number
        debug_assert!(num > 0, "Attempting to remove from an empty position: pos={}, seq={:?}", pos, seq);

        // Ensure correct removal of the second occurrence
        if num > 1 {
            let second_pos = pos + num as usize;
            debug_assert!(
                second_pos < seq.len() && seq[second_pos] == num,
                "Invalid state: expected second occurrence of {} at position {}, seq={:?}",
                num, second_pos, seq
            );
            seq[second_pos] = 0;
        }

        seq[pos] = 0;
    }
}