题目描述

在坡地上开挖一个个不一定相同的坑池，坑池上方左右两边的引水沟斜横在坡地上，将雨水引流到坑池内，在围埂的邦助下保护雨水的流失，溢水口将超出坑池乘载范围内的水量自行排出坑池，达到安全合理有效保留坡地上的雨水资源，防止雨水资源的流失，有利于防旱涝，造福于人类。

给定一个直方图(类似于坑池)，假设下了一场大雨坡地上的坑池都装满了水，问直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）

输入格式

输入多行数据，第一行包含整数 \(T\)，表示有 \(T\) 个样例，接下来的 \(T\) 个样例，每组数据的第一行包含整数 \(N\)，第二行包含 \(N\) 个整数表示直方图的高度，分别用空格隔开。

输出格式

输出每组数据接收的雨水的体积。

样例

样例输入

1
12
0 1 0 2 1 0 1 3 2 1 2 1

样例输出

6