{"raw_statement":[{"iden":"statement","content":"\n\n地表坑洼不平，每当暴雨来临地面上都会有一个个水洼。   \n又有一场暴雨即将来临，你决定改造地面来减少积水。     \n地面可抽象为一个长度为 $n$ 的正整数序列 $a$，其中 $a_i$ 表示当地的海拔高度。       \n下暴雨时将会汇聚在低洼处无法向两侧流走，比如一个序列 $a=[3,1,5,1,2,3]$。     \n在下雨后的积水如图所示（有 $5$ 格积水）：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/79on2oe3.png)\n\n由于人手不足，现在只来得及改变一个地方的海拔高度为任意正整数。\n\n问改造后积水最少有几格。\n\n\n\n\n"},{"iden":"input","content":"第一行一个整数 $T$。    \n接下来共 $T$ 组数据，每组数据占两行。     \n对于每组数据，第一行一个整数 $n$，表示序列长度。     \n第二行 $n$ 个整数，表示序列 $a$。"},{"iden":"output","content":"对于每组数据输出一行一个整数，最小的积水格数。"},{"iden":"note","content":"对于前 $5\\%$ 的数据，$1\\le n\\le 5$。       \n对于前 $20\\%$ 的数据，$1\\le \\sum  n\\le 550$，$1\\le a_i\\le 500$。     \n对于前 $35\\%$ 的数据，$1\\le \\sum n\\le 5050$，$1\\le a_i\\le 5000$。    \n对于前 $50\\%$ 的数据，$1\\le \\sum n\\le 5050$，$1\\le a_i \\le 10^9$。  \n对于 $100\\%$ 的数据，$1\\le n,\\sum n\\le 10^6$，$1\\le a_i\\le 10^9$。\n\n保证 $1\\le T\\le 10^4$。"}],"translated_statement":null,"sample_group":[["3\n6\n3 2 1 1 2 3\n6\n1 1 4 5 1 4\n6\n1 9 1 9 8 10","2\n0\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}