填空题

木板接水

Question

【题目】
空地上竖立着n个从左到右排列的木板，它们可以把水挡住，但溢出最边上木板的水将会流到空地上。
已知木板间距都是单位1，现给定每个木板的高度，请求出总共能接住的水量？
说明一点，这里只考虑间距（宽度）和高度，不考虑第三个维度，因此水量是平方单位。

示例1，木板高度分别是2,1,3，那么我们可以接住2*2=4平方单位的水，如下图所示。注意，中间那个木板被水淹没了。
    |
|- -|
|-|-|

示例2，木板高度分别是2,4,3，那么可以接住2*1+3*1=5平方单位的水，如下图所示。
  |
  |-|
|-|-|
|-|-|


输入描述： 第一行一个正整数T，表示T个测试样例；
对于每个测试样例，
输入正整数n（n<=1e5），表示n块木板；
接下来输入n个正整数，表示木板高度h（h<1e4）。输入样例： 2 3 2 1 3 3 2 4 3 输出描述： 输出T行，每行一个正整数，表示每个样例能接住的最大平方单位的水量。输出样例 4 5