Unique elements problem

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    
    # dp table
    dp = [[0]*n for _ in range(n)]
    
    # precompute max for all subarrays
    max_arr = [[0]*n for _ in range(n)]
    for i in range(n):
        max_arr[i][i] = arr[i]
        for j in range(i+1, n):
            max_arr[i][j] = max(max_arr[i][j-1], arr[j])
    
    # fill dp
    for length in range(1, n+1):
        for l in range(n - length + 1):
            r = l + length - 1
            
            turn = n - (r - l)
            
            if l == r:
                dp[l][r] = arr[l]*turn + arr[l]
            else:
                left = arr[l]*turn + max_arr[l][r] + dp[l+1][r]
                right = arr[r]*turn + max_arr[l][r] + dp[l][r-1]
                dp[l][r] = max(left, right)
    
    print(dp[0][n-1])