P17299 [ICPC 2026 Xi'an I] Split Sticks

Yuki 的面前有 $n$ 根木棍排成一排，第 $i$ 根木棍的长度为 $a_i$。 Yuki 定义一次操作为： - 选择一根木棍，并将其切成长度均为整数的两部分，其中一部分的长度可以为 $0$。 - 将切成的左半部分木棍合并到这根木棍左边的第一个木棍；若其左边没有木棍，则左半部分木棍单独作为一根新的木棍。 - 将切成的右半部分木棍合并到这根木棍右边的第一个木棍；若其右边没有木棍，则右半部分木棍单独作为一根新的木棍。 - 删除所有长度为 $0$ 的木棍。 现在，Yuki 想进行若干次操作，使得所有木棍的长度均相等。你需要帮助 Yuki 求出，使所有木棍的长度均相等所需的最小操作次数。 可以证明，一定存在至少一种操作方案能够使所有木棍的长度均相等。

本题包含多组测试数据。 第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。 对于每组测试数据： - 第一行包含一个正整数 $n$ $(1 \le n \le 10^6)$。 - 第二行包含 $n$ 个正整数 $a_1, \dots, a_n$ $(1 \le a_i \le 10^6)$。 保证所有测试数据中 $n$ 的总和不超过 $10^6$。

对于每组测试数据，输出一行，包含一个整数，表示使所有木棍的长度均相等所需的最小操作次数。

对于第 $1$ 组测试数据： - 第 $1$ 次操作选择第 $2$ 根木棍进行操作，将其分成长度为 $4,1$ 的两段，此时从左到右的木棍长度分别为 $5,5$，所有木棍的长度均相等。 - 可以证明使所有木棍的长度均相等所需的最小操作次数为 $1$ 次。 对于第 $2$ 组测试数据： - 第 $1$ 次操作选择第 $1$ 根木棍进行操作，将其分成长度为 $0,1$ 的两段，此时从左到右的木棍长度分别为 $5,2,5$。 - 第 $2$ 次操作选择第 $2$ 根木棍进行操作，将其分成长度为 $1,1$ 的两段，此时从左到右的木棍长度分别为 $6,6$，所有木棍的长度均相等。 - 可以证明使所有木棍的长度均相等所需的最小操作次数为 $2$ 次。 对于第 $3$ 组测试数据： - 初始时所有木棍的长度均相等，故使所有木棍的长度均相等所需的最小操作次数为 $0$ 次。