题目描述

给定一个 $n$ 个元素的序列 $a$，可以进行如下操作，如果选出来两个下标 $i$ 和 $j\ (i < j)$，并且满足 $a_i, a_{i+1}, … a_{j-1}$ 都大于 $0$，可以将 $a_i$ 减 $1$，$a_j$ 加 $1$，输出将 $a_1, a_2, … a_{n-1}$ 都变为 $0$ 至少需要几次操作。

本题数据量较大，建议采用较快的输入输出方式。

输入格式

第一行输入一个整数 $t$，表示测试数据个数。

第二行开始有 $t$ 组测试数据，每组测试数据第一行输入一个整数 $n$，第二行输入 $n$ 个整数。

$1\le t\le 100$，$2\le n\le 100000$，$0\le a_i\le 10^9$。

输出格式

每个测试数据输出一行，表示最少的操作次数。

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

5
11