这种不对称操作还挺恼人的。

写了一个看着很对的贪心做法，但是好像是伪的，看来我是纯纯的$\text{joker}$了。

这题难点在于将博弈问题转化为图论问题。但是不看题解好像真的很难往这方面去想。 不妨考虑原数组的差分序列，每次操作相当于去掉队尾的元素或者让队首的元素$-1$。设$F(x,y)$表示在队首操作了$x$次，队尾操作了$y$次后的状态下必败还是必胜，因为只有这两种状态所以就不用$SG$函数去表示了。说实话$AGC$博弈论题目中很少有这样能定量计算的，所以一般能定量算的情景都需要定量算。

不妨将终止节点写出来，容易发现$(\sum d_i-1,n-i)$是终结点，为必败态。将横纵坐标交换一下，使用笛卡尔坐标系，这样终结点以下的点是合法节点。考虑从上往下合并，维护这一行的所有状态，仔细观察一下，发现就是将序列左移一位，然后在末尾添加一个$0/1$。这个结论是可以严格证明的，因为我们发现任意时刻不会有两个相邻的$0$，以及连续的$1$的长度不会超过$2$，因此归纳法可证。上面规律并不难观察，只要你手玩了足够多组数据。 那么直接模拟即可，复杂度$O(n)$。

算了还是写一个证明吧。只需证明$F(x,y)=F(x-1,y+1)$即可。如果$F(x-1,y)=0$那么根据没有两个相邻的$0$的结论是满足的，如果$F(x-1,y)=1$，那么当$F(x-1,y+1)=1$时算出来就是$1$，当$F(x-1,y+1)=0$时算出来就是$0$。因为是平移所以序列$F(x)$和$F(x-1)$的性质不会发生变化，这样就证完了。

细节决定成败。实际上 终止点的数目是可能$<n$的 ，换句话说同一行只保留最右边那么一个作为终止点。那么每次要在开头插入一段$01$交错的序列。事实上我想复杂了，并没有必要维护整个序列的状态，只用求$x=y$这条对角线上任意某一点的状态来代替$(0,0)$即可。

复杂度$O(n)$。