#P18557. Exchanging Kubic 3

Exchanging Kubic 3

Exchanging Kubic 3

小青鱼正在与 Kubic 教授进行一项社会实验。有一排 nn 个格子,从 11 到 nn 编号。长度为 nn 的整数数组 aa 描述士兵的分布。对于格子 ii:

  • 若 ai=0a_i=0,该格为空。
  • 若 ai>0a_i>0,该格有 aia_i 名好士兵。
  • 若 ai<0a_i<0,该格有 −ai-a_i 名坏士兵。

小青鱼可以进行若干次操作。每次选择下标 i,ji,j,满足 1≤i,j≤n1\le i,j\le n、ai>0a_i>0,并且 jj 与 ii 相邻,即 j∈{i−1,i+1}j\in\{i-1,i+1\}。将格子 ii 的全部士兵移动到格子 jj,执行:

aj←aj+ai,ai←0.a_j\leftarrow a_j+a_i,\qquad a_i\leftarrow0.

小青鱼讨厌坏士兵,希望消灭所有坏士兵,也就是使所有 1≤i≤n1\le i\le n 都满足 ai≥0a_i\ge0。

求达到目标需要的最少操作次数;如果不可能,报告无解。只能移动严格正的整堆,不能移动负格或空格,也不能只移动一部分。

输入格式

输入含多组测试。第一行一个整数 TT(T≥1T\ge1),表示测试组数。每组测试:

  • 第一行一个整数 nn(1≤n≤5×1051\le n\le5\times10^5),表示格子数量。
  • 第二行 nn 个整数 a1,…,ana_1,\ldots,a_n(−109≤ai≤109-10^9\le a_i\le10^9)。

保证所有测试的 nn 之和不超过 5×1055\times10^5。

输出格式

对于每组测试,如果无法达到目标,输出一行单词 No。

否则,先输出一行单词 Yes,再输出一行一个整数,表示使所有 ai≥0a_i\ge0 的最少操作次数。

完整原样例

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