#P18902. [2026多校联测]小Z爱优化

[2026多校联测]小Z爱优化

题目背景

奋战三星期,造台计算机……

小 Z 手搓的计算机近期成功运行,但是他发现计算机在运行不同任务时所花费的时间相差巨大,因此他希望对计算机的任务处理系统进行一些优化。

题目描述

小 Z 规划了 nn 个依次执行的任务,其中执行第 ii 个任务所花费的时间为 aia_i。

改进后的计算机可以将这 nn 个任务分为若干组,每组包含恰好一个任务,或恰好两个相邻的任务。每一组执行的时间为组中各任务执行时间之和。

小 Z 不希望某两组任务的执行时间相差太大,因此他想知道,在所有分组方式中,各组执行时间的极差的最小值是多少。

输入格式

本题包含多组数据。

第一行包含一个正整数 TT,表示数据组数。

接下来 TT 组数据,每组第一行包含一个正整数 nn,表示任务个数。

第二行包含 nn 个正整数,表示各任务的执行时间。

输出格式

对每组数据,输出一行一个整数,表示答案。

样例 1

2
6
1 1 4 5 1 4
6
1 9 1 9 8 10
3
2

数据范围

对所有数据,保证 1≤T≤1001\le T\le100,1≤n≤2×1051\le n\le2\times10^5,1≤∑n≤1061\le\sum n\le10^6,1≤ai≤1091\le a_i\le10^9。

测试点编号 n≤n\le ∑n≤\sum n\le ai≤a_i\le
1-4 3030 30003000 10910^9
5-9 10001000
10-13 2×1052\times10^5 10610^6 55
14-16 2×1052\times10^5 10910^9
17-20 10610^6