# Problem Description

A rack has $$\n\$$ horizontal compartments. The leftmost compartment is the $$\1^{st}\$$ compartment and the rightmost compartment is the $$\n^{th}\$$ compartment. Each of the compartments of a rack has a colorful item. A section of a rack consists of one or more consecutive compartments.

A section ($$\i^{th}\$$ compartment to $$\j^{th}\$$ compartment where, $$\i \le j\$$) of a rack is visually balanced if the items within the section can be re-arranged in such a way that the color sequence of the items from the $$\i^{th}\$$ compartment to the $$\j^{th}\$$ compartment is same as the color sequence of the items from the $$\j^{th}\$$ compartment to the $$\i^{th}\$$ compartment.

Few examples of visually balanced sections are:

Note that, in the third example, the items in this section can be re-arranged in such a way that the color sequence of the items from the $$\1^{st}\$$ compartment of this section to the compartment of this section will be same as the color sequence of the items from the compartment of this section to the $$\1^{st}\$$ compartment of this section.

Given the colors of each of the $$\n\$$ items of a rack, your task is to determine the number of visually balanced sections of a rack.

### Function Description

Complete the visuallyBalancedSections function in the editor below. It should return an integer denoting the number of visually balanced sections of a rack..

visuallyBalancedSections has the following parameter(s):

colors: an integer array representing the colors of item in each compartment

### Input Format

• The first line contains a single integer $$\t\$$ denoting the number of scenarios.
• The first line of each scenario contains a single integer $$\n\$$ denoting the number of compartments of a rack.
• Each of the next line $$\i\$$ of the $$\n\$$ subsequent lines (where $$\1 \le i \le n\$$) of a scenario contains an integer $$\color\$$ denoting the color of the item in the $$\i^{th}\$$ compartment.

### Constraints

• $$\1 \le t \le 100\$$
• $$\1 \le n \le 1000\$$
• $$\1 \le color \le 50\$$

### Output Format

• For each scenario, print an integer denoting the number of visually balanced sections of a rack.

### Sample Input 0

1
4
1
2
1
2


### Sample Output 0

7


### Explanation 0

There is only one scenario where the rack has four compartments.

• The $$\1^{st}\$$ compartment has an item of $$\= 1\$$.
• The $$\2^{nd}\$$ compartment has an item of $$\= 2\$$.
• The $$\3^{rd}\$$ compartment has an item of $$\= 1\$$.
• The $$\4^{th}\$$ compartment has an item of $$\= 2\$$.

The visually balanced sections are:

1. {$$\\{1\}\$$} - compartment 1
2. {$$\\{2\}\$$} - compartment 2
3. {$$\\{1\}\$$} - compartment 3
4. {$$\\{2\}\$$} - compartment 4
5. {$$\\{1, 2, 1\}\$$} - compartments 1, 2 and 3
6. {$$\\{2, 1, 2\}\$$} - compartments 2, 3 and 4
7. {$$\\{1, 2, 1, 2\}\$$} - compartments 1, 2, 3 and 4

This current solution times out. I have an idea for a faster solution with memoisation, but I'm still working on it so I decided to submit this for review in the interim.

## Current Solution

from collections import defaultdict
from copy import copy

def is_palindrome(counter):
return len(list(filter(lambda x: x%2, counter.values()))) == (1 if sum(counter.values()) % 2 else 0)

def visuallyBalancedSections(colours):
counter = defaultdict(lambda: 0)
total = 0
for i, val in enumerate(colours):
counter[val] += 1
temp_counter = copy(counter)
for j in range(i+1):
total += int(is_palindrome(temp_counter))
temp_counter[colours[j]] -= 1