#include <iostream>

int GetWater(int * pBoardHeight, int iLeft, int iRight);

int main()
{
    int i_test_count;//测试用例数
    std::cin >> i_test_count;
    int * p_board_count = new int[i_test_count];//每个测试用例木板数数组

    int ** p_board_height = new int *[i_test_count];//木板高度数组
    for (int i = 0; i < i_test_count; i++)
    {
        std::cin >> p_board_count[i];
        p_board_height[i] = new int[p_board_count[i]];
        for (int j = 0; j < p_board_count[i]; j++)
        {
            std::cin >> p_board_height[i][j];
        }
    }

    for (int i = 0; i < i_test_count; i++)
    {
        std::cout << GetWater(p_board_height[i], 0, p_board_count[i] - 1) << std::endl;
    }

    if (p_board_height)
    {
        for (int i = 0; i < i_test_count; i++)
        {
            if (p_board_height[i])
            {
                delete[] p_board_height[i];
                p_board_height[i] = NULL;
            }
        }
    }
    delete[] p_board_height;
    p_board_height = NULL;

    return 0;
}

int GetWater(int * pBoardHeight, int iLeft, int iRight)
{
    int i_max_1 = 0;
    int i_max_1_index = 0;
    int i_max_2 = 0;
    int i_max_2_index = 0;
    for (int i = iLeft; i <= iRight; i++)
    {
        if (pBoardHeight[i] > i_max_1)
        {
            i_max_1 = pBoardHeight[i];
            i_max_1_index = i;
        }
    }

    for (int i = iLeft; i <= iRight; i++)
    {
        if ( (pBoardHeight[i] > i_max_2 && pBoardHeight[i] != i_max_1) 
            || (pBoardHeight[i] == i_max_1 && i != i_max_1_index) )
        {
            i_max_2 = pBoardHeight[i];
            i_max_2_index = i;
        }
    }

    int mid_1 = (i_max_1_index < i_max_2_index) ? i_max_1_index : i_max_2_index;
    int mid_2 = (i_max_2_index > i_max_1_index) ? i_max_2_index : i_max_1_index;
    int sum = (mid_2 - mid_1) * i_max_2;
    if (mid_2 < iRight) sum += GetWater(pBoardHeight, mid_2, iRight);
    if (mid_1 > iLeft) sum += GetWater(pBoardHeight, iLeft, mid_1);
    return sum;
}