题目描述

给一个元素个数为 $n$ 的序列 $a$，你可以选出下标为 $i$ 和 $j(i<j)$ 的两个数，满足 $a_i,a_{i+1},\cdots,a_{j−1}$ 都大于 $0$，此时可以将 $a_i$ 减 $1$，$a_j$ 加 $1$，问最少多少次操作能使 $a_1,a_2,...,a_{n-1}$ 均等于 $0$。

输入格式

第一行一个整数 $t$ 代表数据组数。

对于每组数据，第一行为一个整数 $n$ ；第二行 $n$ 个整数，第 $i$ 个数代表 $a_i$。

输出格式

对于每组数据输出一行一个整数，为最小的操作数。

$1 \le t\le 10^4,2 \le n\le 2\times 10^5,0 \le a_i \le 10^9$

题目保证所有数据的 $n$ 之和不超过 $2\times 10^5$。

样例

4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10

3
5
11
0