小c在家无事可做，决定把书柜里的书重新整理一遍，在不改变书的次序的情况下，使得所有书的高度从左到右单调不减。 遗憾的是书柜没有隔层。为了达到目标，小c只能把相邻的两本书叠在一起，外观上形成一本新的书，新书的高度为原来两本书高度之和。例如书柜有5本书，高度依次为1,3,4,2,1，小c可以选择把第3本书和第4本书叠起来，使得新序列的高度为1,3,6,1。叠过的书还可以再叠，例如上面的序列可以继续变为1,3,7。 现在已知书柜里共有$n$本书，第$i$本书的高度为$a_i$。小c想要在满足书高度单调不减的情况下，让最后一本书的高度最小。你能算出这个最小高度吗？
第一行为一个整数 $T\ (1\leq T\leq 5000)$，表示接下来有 $T$ 组数据。
每组数据有两行，第一行为一个整数 $n\ (1\le n\le 10^5)$，表示共有$n$本书。
第二行为 $n$ 个整数 $a_1,a_2,\dots ,a_n\ (1\le a_i\le 10^9)$，第$i$个数表示书柜中从左往右数第$i$本书的高度。
数据保证 $n$ 的总和不超过 $2\times 10^5$。
对于每组数据，输出一个整数，表示满足要求的情况下最后一本书的高度，占单独一行。
4 6 1 2 3 2 1 4 6 7 3 7 3 3 7 8 1 2 3 4 15 14 17 75 4 3 2 1 3\n \n · · · · · \n \n · · · · · \n \n · · · · · · · \n \n · · · \n
4 10 75 3\n \n \n \n
第一个样例中，合并第4和第5本书，使得序列变为1,2,3,3,4，满足要求；
第二个样例中，最后序列变为10,10,10,10；
第三个样例中，合并第6和第7本书，或者合并前7本书，答案均为75；
第四个样例中，合并第2和第3本书，序列变为3,3,3。