JOI2020遗迹

先考虑如何计算一个序列操作n次后的结果。

注意到序列最后一个数是一定不会变的。

进一步，序列最后且“没有相同的数在它右边”的数是不会变的。

只有“有相同的数在它右边”的数会变化。

实际上，摧毁的过程可以被描述为以下代码：

vis[i]表示第i种数是否在右边出现。

for(int i=2*n;i;i--){
    while(vis[a[i]])a[i]--;
    vis[a[i]]=1;
}

这样子是正确的（不用考虑时间），是因为如果右边有一个数占据了这个数的位置，这个数一定会-1。

这样子就可以从右往左dp了。

设f[i][j]表示从i~2*n填数，数组中1~j被占据的方案数。