题目重述 我们有一个数组，由 $n$ 个“块”压缩表示：第 $i$ 个块是 $a_i$ 个连续的 $b_i$。 保证相邻块的值不同：$b_i \neq b_{i+1}$。

每一秒，同时删除所有满足以下条件的元素：

它是数组的第一个元素，或者

它不等于它左边的元素

删除后，剩余部分按原顺序拼接。

定义数组的“强度”为它变为空数组所需的秒数。

对于每个前缀 $i = 1, 2, \dots, n$，求该前缀所描述数组的强度。

核心观察

1. 理解删除规则 规则等价于：每一秒，每个“连续相同值”的块中，只保留最左边的那个元素，其余都被删除。

例如，块 $[x, x, x, x]$ 有 $4$ 个 $x$：

第 $1$ 秒后：只剩第一个 $x$

第 $2$ 秒后：第一个 $x$ 还在（因为它是新的第一个），但块只剩它自己，所以这一秒它也会被删除？ 让我们仔细模拟：

初始：$[x, x, x, x]$

第 $1$ 秒：删除 $i=2,3,4$（因为 $i=1$ 保留，$i=2$ 与 $i=1$ 相等所以删除？不对！规则是 $i=1$ 或 $s_i \neq s_{i-1}$ 才删除。$s_2 = x$，$s_1 = x$，相等，所以 $s_2$ 不满足删除条件！）

等等，我理解错了。让我重新解读规则：

所有 $s_i$ 使得 $i=1$ 或 $s_i \neq s_{i-1}$ 会被删除。

这意味着：

第一个元素（$i=1$）一定被删除。

对于 $i>1$，如果 $s_i \neq s_{i-1}$（即它是某个连续段的新开头），则它也被删除。

如果 $s_i = s_{i-1}$（即它在连续段内部），则它不被删除。

所以实际上，每一秒，所有“连续段的最左边元素”都被删除，而连续段内部的元素保留。

例：$[0,0,1,0,0,0,1,1,1,1,1]$

连续段：$[0,0]$, $[1]$, $[0,0,0]$, $[1,1,1,1,1]$

最左边元素：第一个 $0$，第一个 $1$，第一个 $0$，第一个 $1$ → 这些被删除

剩下：$[0, 0, 0, 1,1,1,1]$（原来每个段去掉第一个后剩下的）

这与题目给的示例一致。

2. 块的生命周期 对于一个长度为 $a$ 的块（$a$ 个相同值）：

每一秒，该块的长度减少 $1$（因为最左边那个被删了）

所以仅考虑这个块自己，它需要 $a$ 秒才能完全消失。

但块之间会相互影响。考虑相邻的两个块 $X$（值 $v$，长度 $a$）和 $Y$（值 $w$，长度 $b$），且 $v \neq w$。

在 $X$ 存在的每一秒，$Y$ 的第一个元素都会被删除（因为 $Y$ 的第一个元素 $\neq$ 它的左边元素，即 $X$ 的最后一个元素，只要 $X$ 还存在）。 所以只要 $X$ 还在，$Y$ 的长度每一秒也会减少 $1$（因为它的第一个元素被删了，但 $Y$ 内部剩余元素仍然连续）。

更精确地说：

当 $X$ 和 $Y$ 都存在时，每一秒：$X$ 长度减 $1$，$Y$ 长度减 $1$。

当 $X$ 先消失后，$Y$ 成为新的最左块（或者前一个块是别的），但它的剩余长度需要继续减少。

这提示我们：一个块的“剩余时间”依赖于它左边块的生命周期。

算法思路 我们可以从左到右处理块，维护一个栈。栈中每个元素表示一个“活着的”块，记录它的剩余长度和它的值。

对于新块 $(a, b)$：

如果栈顶的值等于 $b$，则合并：将 $a$ 加到栈顶的长度上，然后弹出栈顶（因为合并后需要重新计算）。

否则，我们需要计算这个新块需要多少秒才能消失。设当前栈顶块的长度为 $len_{top}$，值为 $b_{top} \neq b$。

只要栈非空且栈顶块的长度 $\le a$，则栈顶块会先于当前块消失。在此期间，当前块每一秒也减少 $1$。 所以当栈顶块消失时，当前块已经消耗了 $len_{top}$ 秒，剩余长度为 $a - len_{top}$。

但更关键的是，当前块的“生存时间”必须至少为 $len_{top} + 1$（因为栈顶块消失后，当前块成为新的比较对象）。

实际上，我们需要维护的是：当前块需要的时间 = $\max(a, \text{栈顶时间} + 1)$，但这里栈顶时间指的是栈顶块完全消失所需的时间。

正确做法是维护每个块“完全消失所需的时间”。设 $f_i$ 为第 $i$ 个块（从左到右处理后的块）的消失时间。

当我们加入一个新块 $(a, b)$ 时：

如果与栈顶值相同，合并：$a$ 增加，栈顶弹出，然后重新计算这个合并块的时间。

否则，新块的消失时间初始为 $a$。然后看栈顶：

如果栈顶的消失时间 $\le$ 当前块的消失时间，则栈顶会在当前块之前或同时消失。但当前块会“等待”栈顶消失后才成为新的左端，所以当前块的消失时间至少为栈顶消失时间 $+1$。 因此，更新当前块消失时间为 $\max(\text{当前时间}, \text{栈顶时间} + 1)$，然后弹出栈顶（因为栈顶已经被“覆盖”）。

重复直到栈空或栈顶消失时间 $>$ 当前块消失时间。

然后将当前块 $(a, b)$ 以消失时间压栈。

最后，整个前缀的答案就是栈底（第一个块）的消失时间。

时间复杂度 每个块最多入栈出栈一次，$O(n)$。