extension Array {
    // in:  [1, 2, 3, 4]
    // out: (1, [2, 3, 4])
    var decompose :(head: Element, tail: [Element])? {
        return (count > 0) ? (self[0], Array(self[1..<count])) : nil
    }
}

// in:  0, [1, 2, 3]
// out: [[0, 1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3], [1, 2, 3, 0]]
func between<T>(_ x: T, _ ys: [T]) -> [[T]] {
    if let (head, tail) = ys.decompose {
        return [[x] + ys] + between(x, tail).map { return [head] + $0 }
    } else {
        return [[x]]
    }
}

// in:  [1, 2, 3]
// out: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
func permutations<T>(_ xs: [T]) -> [[T]] {
    if let (head, tail) = xs.decompose {
        return permutations(tail).flatMap { permTail in
            return between(head, permTail)
        }
    } else {
        return [[]]
    }
}

func q1(_ input: Int, _ args: [Int]) -> Int {
    var maxSum = -1
    let perm = permutations(args)
    perm.forEach {
        var sum = 0
        var i = 0
        while i < $0.count {
            sum += min($0[i], $0[i + 1])
            i += 2
        }
        if sum > maxSum {
            maxSum = sum
        }
    }
    return maxSum
}



