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:
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$$$.
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$$$.
For each test case, print a single integer — the sum of the values of the function $$$f$$$ for all subarrays of the array $$$a$$$.
432 1 341 1 1 154 2 3 1 541 2 1 2
3 0 14 5
Name |
---|