solution
神仙 dp 题。
下文认为 \(n\) 是题目中给定 \(n\) 的两倍。
先考虑一个给定的序列是否能被消除的条件。
猜测一下应该是
-
序列长度是偶数
-
不存在一个数，在序列中出现超过 \(\lfloor\dfrac{n}{2}\rfloor\) 次，其中 \(n\) 是序列长度。
必要性是显然的。我们每次尽可能消出现次数最多的数，如果满足条件 2，那么当然也是可以消完的（消掉两个数后变成了子问题），所以也有充分性。
设 \(f_i\) 表示考虑前 \(i\) 个数的答案，有转移：
-
\(f_0=1\)
-
\(f_{2k+1}=0\)
-
\(f_{2k}=\sum\limits_{i=0}^{2k-1} [2\mid i][\texttt{chk}(i+1,2k)]f_i\)，\(\texttt{chk}(l,r)\) 表示区间 \((l,r)\) 是可消的。
对于第三个式子，固定 \(2k\)，从后往前扫，可以顺便维护 \(\texttt{chk}\)，时间复杂度 \(O(n^2)\)。
考虑如何优化转移。
打表发现转移没有什么好的性质，每次转移点变化量之和也是不太能接受的大小。
考虑使用 CDQ 分治优化转移（比较突兀哈，zyb 猜的做法，后来发现可以做）。
对于区间 \([l,r]\)，设它分成 \([l,mid]\) 与 \([mid+1,r]\) 两个区间，由于是从前向后算，先递归求出 \([l,mid]\) 内所有 dp 值，然后考虑区间 \([l,mid]\) 对区间 \([mid+1,r]\) 的贡献。
这样做有很好的性质。
性质：对于所有 \([L,R],l\leq L\leq mid,mid+1\leq R\leq r\)，可能的出现次数大于区间一半的数的种类只有 \(O(\log(r-l))\) 个。
对于证明，先考虑一个前置结论：
一个序列任意前后缀的出现次数大于区间长度一半的数的种类只有 \(O(\log n)\) 个，\(n\) 是序列长度。
比较容易看出，就不证了。
\([L,R]\) 相当于 \([l,mid]\) 的一个后缀和 \([mid+1,r]\) 的一个前缀拼起来，这样数的种类也就不超过 \(O(\log(r-l))\) 个了。
这样就允许我们在计算贡献的时候枚举这样的数了。
注意，这些非法的转移的贡献是负的，要先把所有 \(i<p\) 的 \(f_i\) 贡献到 \(f_p\) 上，然后在根据下面的做法减去这些非法转移的贡献。
枚举左端点，然后枚举这些数，用数据结构维护贡献。
具体实现流程如下：
下面设区间长度为 \(m\)。
先处理出来这样的数，去重。可以 \(O(m\log m)\) 做到。（\(\log\) 是去重时排序给的），设有 \(sz\) 个这样的数。
设一个这样的数 \(p\) 的前缀出现次数是 \(c_{p,i}\)，则区间 \([l,r]\) 能因为这个数不合法的条件就是 \(\dfrac{r-l+1}{2}<2c_{p,r}-2c_{p,l-1}\)，整理得 \(2c_{p,l-1}-(l-1)<2c_{p,r}-r\)。所以我们不妨给每个数 \(sz\) 个权值，数 \(p\) 在 \(i\) 位置的对应权值就是 \(2c_{p,i}-i\)。然后开 \(sz\) 个差分数组，整个分治区间内的数按照 \((2c_{p,i},i)\) 第一关键字递增，第二关键字递减（第二关键字递减是为了让 \([l,mid]\) 内的数排到后面，处理 \(<\) 号，而不能取等）。再处理出每个数在这 \(sz\) 个排序后的数组里的下标。都可以 \(O(m\log m)\) 处理好。
枚举不合法左端点，再枚举这 \(sz\) 个数，然后在对应的差分数组里做修改，修改是 \(O(1)\) 的，枚举是 \(O(m\log m)\) 的。
最后把差分数组前缀和一遍，对应 dp 值加上贡献即可。
带上 CDQ 的 \(\log\)，时间复杂度 \(O(n\log^2n)\)。
细节比较多，而且有点卡常（official solution 是 \(O(n)\) 的）。