下面记 $i$ 位置上初始时有 $a_i$ 颗星星。
首先，可以证明任何一个状态可以抵达的终止状态（被定义为无法进行任何操作的状态）是一定的，与操作无关：
证明（credit to Mingxi Lyu 的前男友）：
考虑存在两个合法序列，分别在 $i$ 上操作了 $u_i$ 和 $v_i$ 次，因为序列无法继续操作，则 $a_i-2u_i+u_{i-1}+u_{i+1}\leq 1$。
因为 $u$ 和 $v$ 不同，不妨记录第一次出现某个 $v_i$ 大于 $u_i$ 的位置在 $i$（小于的情况显然是对称的），记录此时状态为 $w$。由于这是第一次超过，所以邻居满足 $w_{i-1}\leq u_{i-1},w_{i+1}\leq u_{i+1}$，那么有：$a_i-2w_i+w_{i-1}+w_{i+1}\leq a_i -2u_i+u_{i-1}+u_{i+1}\leq 1$。
但是要操作 $i$ 至少要有两颗星星，矛盾！
故 $u$ 和 $v$ 相同。
（注：可能更直观的理解方式是：现在不对 $x$ 操作未来也要操作，但这不太好书写，上面的内容实际上在形式化表述这件事）
接下来我们考虑求出最终的稳定状态，这可以通过每次尝试分裂区间完成，我们从小到大插入点，不难发现势能是 $\mathcal O(n)$ 的，使用 map 之类的东西就可以快速维护。
求出稳定状态后，可以简单地求出 $t_i$ 代表 $i$ 位置上被操作了多少次，记稳定状态是 $b$。不妨设 $\operatorname{mex}$ 为 $m$，则如果要让它更大，我们需要进行若干次 $(x-1),(x+1)\to x,x$ 的反向操作。如果想要让 $\operatorname{mex}$ 变大 $k$，我们需要进行若干次反向操作。经过一些推导，以下条件是必要的：
- $b$ 中存在 $-1,m+1,m+2,\cdots m+k$，否则我们无法完成移动。
- 定义 $h_i$ 为 $i$ 被 $[0,m],[1,m+1],\cdots [k-1,k-1+m]$ 中的多少个区间覆盖，则应该有 $t_i\geq h_i$，这是因为我们必须在 $i$ 位置上完成 $h_i$ 次撤销。
我们下面证明这个条件是充分的：
我们从 $b$ 开始依次撤销区间，第 $i$ 次尝试撤销 $[i,i+m]$（我们下文将用 $c$ 来代表当前的状态），我们将会通过一些精细的讨论证明：每个状态都是由初始状态可达的：
我们归纳的证明区间 $[i,i+m]$ 在撤销前始终满足如下结构：$c_{i-1}\geq 1,c_{i},c_{i+1},\cdots c_{i+m-1}=1,c_{i+m}=0,c_{i+m+1}=1$，并且在撤销前，存在一种操作序列使得 $[i,i+1,\cdots,i+m]$ 是操作序列的后缀。
首先我们证明如果满足上述结构，那么一定存在操作序列使得 $[i,i+1,\cdots,i+m]$ 是操作序列的后缀：这是因为 $i+m$ 位置一定被操作过。且 $i+m$ 是否操作只会影响 $i+m\pm 1$ 能否操作。但是最后 $i+m$ 位置为 $0$，故 $i+m$ 最后一次操作后一定没有 $i+m\pm 1$ 影响它，故我们可以将对 $i+m$ 的操作调整至最后！随后我们撤销 $i+m$ 的操作，此时 $i+m-1$ 变为 $0$！依次向前递推便可以撤销掉这个区间的操作。我们发现操作后 $[i+1,i+m]$ 变为 $1$，$i+m+1$ 变为 $0$。同时因为对 $b$ 的判定，$i+m+2$ 是 $1$。故符合我们的归纳假设。
因此条件是充分的，证毕。
二分检查上述条件即可，复杂度 $\mathcal O(n\log n)$。