Little Cyan Fish 正在与 Prof. Kubic 进行一项社会实验。实验中有一排编号从 $1$ 到 $n$ 的格子。一个长度为 $n$ 的整数数组 $a$ 描述了这些格子中士兵的分布情况。对于每个格子 $i$：

• 如果 $a_i = 0$，则格子 $i$ 为空。
• 如果 $a_i > 0$，则格子 $i$ 包含 $a_i$ 个好士兵。
• 如果 $a_i < 0$，则格子 $i$ 包含 $-a_i$ 个坏士兵。

Little Cyan Fish 可以执行若干次操作。在一次操作中，Little Cyan Fish 可以选择两个满足 $1 \le i, j \le n$ 的下标，且满足 $a_i > 0$ 且 $j$ 与 $i$ 相邻（即 $j \in \{i - 1, i + 1\}$）。随后，该操作通过执行以下更新将格子 $i$ 中的所有士兵移动到格子 $j$：

$$a_j \leftarrow a_j + a_i, \quad a_i \leftarrow 0$$

Little Cyan Fish 讨厌坏士兵，因此他想要消灭所有坏士兵。换句话说，他需要达到：

$$a_i \ge 0 \quad \text{对于所有 } 1 \le i \le n$$

请确定达到目标所需的最少操作次数，如果无法达到，请报告。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($T \ge 1$)，表示测试用例的数量。每个测试用例的格式如下：

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)，表示格子的数量。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示格子中士兵的分布。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例：

如果无法达到 Little Cyan Fish 的目标，输出一行，内容为 “No”。

否则，第一行输出 “Yes”。

下一行输出一个整数，表示确保对于所有 $1 \le i \le n$ 都有 $a_i \ge 0$ 所需的最少操作次数。

样例

样例输入 1

4
2
-2 1
3
1 0 -1
5
-1 4 -1 -1 -1
6
-1 2 -1 -1 3 -1

样例输出 1

No
Yes
2
Yes
5
Yes
5