{"problem":{"name":"「LAOI-1」积水","description":{"content":" 地表坑洼不平，每当暴雨来临地面上都会有一个个水洼。    又有一场暴雨即将来临，你决定改造地面来减少积水。      地面可抽象为一个长度为 $n$ 的正整数序列 $a$，其中 $a_i$ 表示当地的海拔高度。        下暴雨时将会汇聚在低洼处无法向两侧流走，比如一个序列 $a=[3,1,5,1,2,3]$。      在下雨后的积水如图所示（有 $5$ 格积水）： ![](https","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9485"},"statements":[{"statement_type":"Markdown","content":"地表坑洼不平，每当暴雨来临地面上都会有一个个水洼。   \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## Input\n\n第一行一个整数 $T$。    \n接下来共 $T$ 组数据，每组数据占两行。     \n对于每组数据，第一行一个整数 $n$，表示序列长度。     \n第二行 $n$ 个整数，表示序列 $a$。\n\n## Output\n\n对于每组数据输出一行一个整数，最小的积水格数。\n\n[samples]\n\n## Note\n\n对于前 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9485","tags":["模拟","洛谷原创","O2优化","前缀和"],"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"]],"created_at":"2026-03-03 11:09:25"}}