题号：NC26000
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
题目描述
你是DEEP国的大军师，辅佐一个非常有野心的国王，这位国王非常有野心，他计划攻占 n 个国家。在地图上，这些国家排成一行。
探子已经查明，当攻打一个国家 i 时，为了防止国家间的联合对抗，需要给该国家周围，所有未被攻占的国家支付
个金币，即对于国家 i，它左侧第一个已被攻打的国家为 l，右侧第一个已被攻打的国家为 r，则他需要给[l+1,i-1] 和 [i+1,r-1] 之间的国家支付金币。如果 l 不存在，则需要给 [1, i-1] 之间的所有国家支付金币；若 r 不存在，则需要给 [i+1,n] 之间的所有国家支付金币。
现在，你的下属已经给你提供了每个国家需要支付金币的数量。为了满足国王的野心，你需要计算出攻占完所有国家需要的最小花费。
探子已经查明，当攻打一个国家 i 时，为了防止国家间的联合对抗，需要给该国家周围，所有未被攻占的国家支付
现在，你的下属已经给你提供了每个国家需要支付金币的数量。为了满足国王的野心，你需要计算出攻占完所有国家需要的最小花费。
输入描述:
第一行是一个整数 T，代表接下来有T组数据。
接下来每组数据
第一行有一个整数 n，代表要攻占的国家数目。
第二行共 n 个整数，代表攻占每个国家前，需要支付给其周围未被攻占国家，
，
输出描述:
对于每组数据输出一行，代表需要支付的最小花费。