信号屏蔽 (shield)

题目描述

Y 同学正在进行一项秘密信号屏蔽任务。他面前有一个长度为 $N$ 的信号序列 $A = \{a_1, a_2, \ldots, a_n\}$，每个元素 $a_i$ 代表该位置信号的发射强度。

为了使屏蔽效果最佳，Y 同学需要从中挑选若干个位置安装屏蔽器。假设 Y 同学选择安装屏蔽器的下标集合为 $S = \{b_1, b_2, \ldots, b_m\}$，其中 $1 \le b_1 < b_2 < \ldots < b_m \le n$。在安装完成后，整个系统的代价由以下两部分的较大值决定：

1. 屏蔽成本：所有安装了屏蔽器的位置强度之和，即 $P = \sum_{i \in S} a_i$。
2. 泄露风险：在移除所有安装屏蔽器的位置后，剩余信号序列被分割成若干个连续段。泄露风险 $Q$ 定义为这些连续段中各元素强度之和的最大值。形式化地，令 $b_0 = 0$ 且 $b_{m+1} = n+1$，则 $Q = \max_{0 \le i \le m} \left( \sum_{j=b_i+1}^{b_{i+1}-1} a_j \right)$。若某段不包含任何元素（即 $b_i + 1 = b_{i+1}$），则该段的强度之和视为 $0$。

Y 同学希望通过合理选择安装屏蔽器的位置，使得系统的总代价 $\max(P, Q)$ 最小。请你输出这个最小代价。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $N$，表示信号序列的长度。 第二行包含 $N$ 个整数 $a_1, a_2, \ldots, a_n$，表示信号序列中每个位置的强度。

输出格式

对于每组测试数据，输出一行一个整数，表示可能的最小总代价。

样例

样例输入 #1

3
6
1 4 5 3 3 2
5
1 2 3 4 5
6
4 1 6 3 10 7

样例输出 #1

7
5
11

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 3 \times 10^4$，$1 \le N \le 10^5$，$1 \le a_i \le 10^9$。所有测试用例的 $N$ 之和不超过 $10^5$。

• 特殊性质 A：保证序列中所有元素 $a_i$ 均相等。
• 特殊性质 B：保证序列中元素 $a_i$ 满足单调不减，即 $a_i \le a_{i+1}$。