from collections import namedtuple
from functools import cache
from itertools import groupby
from typing import List

BoxRun = namedtuple("Box", ("color", "count"))


class Solution:
    def removeBoxes(self, boxes: List[int]) -> int:
        @cache
        def best_score(boxes, same_as_first_around):
            # Try to take same boxes from the left
            lead_color = boxes[0].color
            same_as_first_around += boxes[0].count
            boxes = boxes[1:]
            # And from the right if they are the same color
            if boxes and boxes[-1].color == lead_color:
                same_as_first_around += boxes[-1].count
                boxes = boxes[:-1]
            if not boxes:  # We took last boxes, just count the points
                return same_as_first_around ** 2
            else:
                # Assume there are no same-color boxes in between
                score = same_as_first_around ** 2 + best_score(boxes, 0)
                for mid in range(1, len(boxes)):
                    # Scan boxes in between looking for same colored boxes
                    if boxes[mid].color == lead_color:
                        # Check if removing boxes to the left first improves the score
                        score_for_removed = best_score(boxes[:mid], 0)
                        score_for_joined = best_score(boxes[mid:], same_as_first_around)
                        score = max(score, score_for_removed + score_for_joined)
                return score

        box_runs = tuple(BoxRun(color, len(list(run))) for color, run in groupby(boxes))
        return best_score(box_runs, 0)