Make a Palindrome
Contest: Educational Codeforces Round 169 (Rated for Div. 2)
Difficulty rating: 2600
Tags: binary search, brute force, data structures, greedy, math

You are given an array $$$a$$$ consisting of $$$n$$$ integers.

Let the function $$$f(b)$$$ return the minimum number of operations needed to make an array $$$b$$$ a palindrome. The operations you can make are:

- choose two adjacent elements $$$b_i$$$ and $$$b_{i+1}$$$, remove them, and replace them with a single element equal to $$$(b_i + b_{i + 1})$$$;
- or choose an element $$$b_i > 1$$$, remove it, and replace it with two positive integers $$$x$$$ and $$$y$$$ ($$$x > 0$$$ and $$$y > 0$$$) such that $$$x + y = b_i$$$.

For example, from an array $$$b=[2, 1, 3]$$$, you can obtain the following arrays in one operation: $$$[1, 1, 1, 3]$$$, $$$[2, 1, 1, 2]$$$, $$$[3, 3]$$$, $$$[2, 4]$$$, or $$$[2, 1, 2, 1]$$$.

Calculate $$$\displaystyle \left(\sum_{1 \le l \le r \le n}{f(a[l..r])}\right)$$$, where $$$a[l..r]$$$ is the subarray of $$$a$$$ from index $$$l$$$ to index $$$r$$$, inclusive. In other words, find the sum of the values of the function $$$f$$$ for all subarrays of the array $$$a$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output format:
For each test case, print a single integer — the sum of the values of the function $$$f$$$ for all subarrays of the array $$$a$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
4
3
2 1 3
4
1 1 1 1
5
4 2 3 1 5
4
1 2 1 2

Example output:
3
0
14
5

Editorial:
To begin with, let's find out how to solve the problem for a single subarray in linear time.
If equal numbers are at both ends, we can remove them and reduce the problem to a smaller size (thus, we have decreased the length of the array by $$$2$$$ in $$$0$$$ operations, or by $$$1$$$ if there is only one element). Otherwise, we have to do something with one of these numbers: either merge the smaller one with its neighbor or split the larger one. It can be shown that it doesn't matter which of these actions we take, so let's split the larger of the two numbers at the ends in such a way that the numbers at the ends become equal, and then we can remove the equal numbers at the ends (thus, we reduce the length of the array by $$$1$$$ in $$$1$$$ operation). In this case, the answer for the array depends on the number of situations where the ends of the array have equal numbers and the number of situations where they are different.
Now let's understand how to quickly calculate how many times, when processing a subarray, we encounter a situation where the ends have equal numbers. After removing these equal numbers at the ends, we obtain a subarray such that numbers with equal sums have been removed from the prefix and suffix compared to the original subarray.
We can determine how many such subarrays can be obtained from the original one by removing a prefix and a suffix with equal sums. For this, we can use prefix sums. Let the prefix sum at the beginning of the segment be $$$p_l$$$, and at the end be $$$p_r$$$. If we remove a prefix and a suffix with sum $$$s$$$, the sums become $$$p_l + s$$$ and $$$p_r - s$$$. At the same time, the sum $$$p_l + p_r$$$ for the smaller subarray remains the same. Therefore, for each such subarray that results from the situation "the elements on the right and left were equal, we removed them" the sum $$$p_l + p_r$$$ is the same as that of the original segment.
To calculate the number of shorter segments with the same sum $$$p_l + p_r$$$ for each segment, we can iterate through all segments in order of increasing length and store in a map the count of subarrays with each sum $$$p_l + p_r$$$. This leads us to solve the problem in $$$O(n^2 \log{n})$$$.